Leetcode 696. Count Binary Substrings

Question: 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

Approach:

In the given LeetCode problem, we are provided with a string consisting of 0s and 1s. Our task is to find the number of non-empty substrings that contain an equal number of 0s and 1s, with all the 0s grouped consecutively and all the 1s grouped consecutively.

Valid substrings include examples like:

• "01"
• "0011"
• "10"
• "1100"

However, a substring like "0101" should not be counted as a valid substring because the 0s and 1s are not grouped consecutively.

That said, "0101" can be divided into smaller valid substrings, such as:

"01"

• "10"
• "01"

Each of these smaller substrings should be counted individually.

Core Idea

We simultaneously count the consecutive occurrences of 0s and 1s.

Instead of checking all substrings (which would be slow), we:

• Count how many times the current character repeats (c)
• Keep track of how many times the previous character repeated (p)
• Whenever the character changes, we add:

min(previous group count, current group count)

Because:

• A valid substring can only be formed between two consecutive groups.
• The number of such substrings depends on the smaller group.

Step-by-Step Algorithm

Step 1:

Initialize:

• p = 0 → previous group count
• c = 1 → current group count (starts from 1 because the first character is already counted)
• res = 0 → result

Step 2:

Convert a string into a character array.

Step 3:

Traverse the string from the index 1 to end:

• If current character == previous character → increase c
• Else:
• Add min(p, c) to result
• Set p = c
• Reset c = 1

Step 4:

After the loop ends, add min(p, c) One last time.

Step 5:

Return result.

class Solution {
public int countBinarySubstrings(String s) {
int p = 0;
int c = 1;
int res = 0;
char[] arr = s.toCharArray();
for (int i = 1; i < s.length(); i++) {
if(arr[i] == arr[i-1]) {
c++;
}else{
res+=Math.min(p,c);
p=c;
c=1;
}
}
res+=Math.min(p,c);
return res;
}
}

Suppose we have: “000111”

Groups:

• 000 → 3
• 111 → 3

Possible substrings:

• "01"
• "0011"
• "000111"

Total = 3 = min(3,3)

If it was: “00011”

Groups:

• 000 → 3
• 11 → 2

We can only form:

• "01"
• "0011"

Total = 2 = min(3,2)

Time and Space Complexity

• Time Complexity: O(n) → We traverse once
• Space Complexity: O(1) → Only variables used