Scale Engineer

Count Binary Substrings

Easy
#0650Time: O(N^2), where N is the length of the string. In the worst case, for each of the N potential centers, the expansion could take up to O(N) time.Space: O(1), as we only use a few variables for pointers and the count.5 companies
Patterns
Two Pointers
Data structures
String
Companies
ByteDanceIBMJ.P. MorganMorgan Stanley

Prompt

Given a binary string s, return 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.

 

Example 1:

Input: s = "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: s = "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

 

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either '0' or '1'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through the string to find all possible "centers" of a valid substring. A center is a point where the character changes, i.e., a "01" or "10" pattern. For each center found, we expand outwards in both directions, checking if the characters match the initial pattern (e.g., '0's to the left, '1's to the right). We count how many valid substrings can be formed by this expansion.

Algorithm

  • Initialize a counter result = 0.
  • Loop through the string s from i = 0 to s.length() - 2.
  • Check if s.charAt(i) != s.charAt(i+1). If they are different, we've found a center.
    • Increment result because we found a valid substring of length 2 (e.g., "01" or "10").
    • Initialize left = i - 1 and right = i + 2.
    • Start a while loop to expand outwards: while (left >= 0 && right < s.length()).
      • Inside the loop, check if s.charAt(left) == s.charAt(i) and s.charAt(right) == s.charAt(i+1).
      • If the characters match the pattern, we've found another valid substring. Increment result, and move the pointers: left--, right++.
      • If they don't match, the expansion for this center is over. Break the inner while loop.
  • After the main loop finishes, return result.

Walkthrough

The core idea is that any valid substring must contain a "01" or "10" boundary. We can iterate through the string with an index i from 0 to n-2. If s[i] is different from s[i+1], we have found a potential center. For example, if we find s[i] = '0' and s[i+1] = '1', we have found the valid substring "01". This is our base case. We then try to expand this substring. We use two pointers, left = i - 1 and right = i + 2. We move left to the left and right to the right as long as s[left] is '0' and s[right] is '1'. For each successful expansion, we find another valid substring (e.g., "0011", "000111", etc.) and increment our count. We repeat this process for all possible centers in the string.

class Solution {    public int countBinarySubstrings(String s) {        int ans = 0;        for (int i = 0; i < s.length() - 1; i++) {            if (s.charAt(i) != s.charAt(i + 1)) {                ans++; // For the base case like "01" or "10"                int left = i - 1;                int right = i + 2;                while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(i) && s.charAt(right) == s.charAt(i + 1)) {                    ans++;                    left--;                    right++;                }            }        }        return ans;    }}

Complexity

Time

O(N^2), where N is the length of the string. In the worst case, for each of the N potential centers, the expansion could take up to O(N) time.

Space

O(1), as we only use a few variables for pointers and the count.

Trade-offs

Pros

  • Simple to understand and implement.

  • It correctly identifies all valid substrings by focusing on their central property.

  • Uses constant extra space.

Cons

  • The time complexity is quadratic, which is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  int countBinarySubstrings(String s) {    int i = 0, n = s.length();    List<Integer> t = new ArrayList<>();    while (i < n) {      int cnt = 1;      while (i + 1 < n && s.charAt(i + 1) == s.charAt(i)) {        ++i;        ++cnt;      }      t.add(cnt);      ++i;    }    int ans = 0;    for (i = 1; i < t.size(); ++i) {      ans += Math.min(t.get(i - 1), t.get(i));    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem