696. Count Binary Substrings
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 58.3%
Problem Breakdown
The problem requires counting the number of non-empty substrings in a binary string s where the substring contains an equal number of consecutive 0’s and 1’s. The key constraints are that all 0’s must be grouped together and all 1’s must be grouped together within each valid substring.
Inputs:
- A binary string
sconsisting only of ‘0’ and ‘1’.
Outputs:
- An integer representing the count of valid substrings.
Implicit Constraints:
- The length of
sis between 1 and 50,000. - Substrings that occur multiple times are counted individually.
Tricky Edge Cases:
- Strings with only one type of character (all ‘0’s or all ‘1’s).
- Strings where no valid substrings exist.
- Strings with alternating characters like “10101”.
Intuition
A brute-force approach would involve generating all possible substrings and checking if they meet the criteria, which is inefficient given the constraints. The key insight is to leverage the fact that valid substrings must have consecutive groups of 0’s and 1’s. By counting the lengths of these consecutive groups, we can determine how many valid substrings can be formed between each pair of adjacent groups.
For example, in “00110011”, the groups are [2 zeros, 2 ones, 2 zeros, 2 ones]. Between the first two groups (2 zeros and 2 ones), we can form 2 valid substrings (“0011” and “01”). Similarly, between the second pair of groups (2 ones and 2 zeros), we can form another 2 valid substrings (“1100” and “10”).
Approach
- Traverse the string to count consecutive groups of ‘0’s and ‘1’s.
- Store the lengths of these groups in a list.
- For each pair of adjacent groups, calculate the number of valid substrings that can be formed by taking the minimum length of the two groups.
- Sum up all such counts to get the final result.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string
s. We traverse the string once to count the groups and then iterate through the list of group lengths. - Space Complexity: O(n) in the worst case, where all characters are different, leading to a list of group lengths equal to the length of the string.
Solution
def countBinarySubstrings(s: str) -> int:
# Step 1: Count consecutive groups of '0's and '1's
counts = []
i = 0
while i < len(s):
count = 1
while i + 1 < len(s) and s[i] == s[i + 1]:
i += 1
count += 1
counts.append(count)
i += 1
# Step 2: Calculate the number of valid substrings between each pair of groups
result = 0
for i in range(1, len(counts)):
result += min(counts[i - 1], counts[i])
return result
Edge Cases Handled
- All ‘0’s or all ‘1’s: The
countslist will have only one element, and the final result will be 0 since no valid substrings can be formed. - Alternating characters like “10101”: Each pair of adjacent groups has a count of 1, so the result will be equal to half the length of the string minus one.
- Empty input: The function handles this gracefully as the while loop condition ensures it doesn’t execute.