algoadvance

Leetcode 696. Count Binary Substrings

Problem Statement

You are given a binary string s (a string consisting only of ‘0’s and ‘1’s). You need to count the number of non-empty substrings that have the same number of ‘0’s and ‘1’s and all the ‘0’s and all the ‘1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Clarifying Questions

  1. Input size and constraints:
    • The length of the string s will be at least 1 and at most ( 50,000 ).
    • The string only contains the characters ‘0’ and ‘1’.
  2. Output:
    • The output should be a single integer representing the count of valid substrings.

Strategy

  1. Identify Group Transitions:
    • Traverse through the string and count consecutive groups of ‘0’s and ‘1’s. Keep track of the lengths of these consecutive groups.
  2. Count Valid Substrings:
    • Every transition from one group to another (from ‘0’ to ‘1’ or ‘1’ to ‘0’) forms potential valid substrings. If there is a transition from a group of a consecutive ‘0’s to a group of b consecutive ‘1’s, then the number of valid substrings is (\min(a, b)). This is because for each position in the smaller group, there is a corresponding valid opposite character from the initial contiguous group.
  3. Calculate the Result:
    • Sum the valid substrings for all transitions from one group to another to get the final result.

Code

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int countBinarySubstrings(string s) {
    vector<int> groups;
    int count = 1;
    
    // Count lengths of consecutive groups
    for (int i = 1; i < s.size(); ++i) {
        if (s[i] == s[i - 1]) {
            ++count;
        } else {
            groups.push_back(count);
            count = 1;
        }
    }
    groups.push_back(count);  // Push the last group
    
    int result = 0;
    // Calculate possible substrings from consecutive groups
    for (int i = 1; i < groups.size(); ++i) {
        result += min(groups[i - 1], groups[i]);
    }
    
    return result;
}

int main() {
    string s = "00110011";
    cout << countBinarySubstrings(s) << endl;  // Output: 6
    return 0;
}

Time Complexity

Thus, the overall time complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI