1. Count Binary Substrings (LeetCode)
Model answer
The task
Count nonempty substrings of a binary string that contain the same number of 0s and 1s, with all the 0s and 1s grouped into consecutive runs.
Key idea
For each pair of neighboring runs, the number of valid substrings they contribute is the length of the shorter run. Track the previous run’s length and the current run’s length, adding the smaller whenever a run ends.
Approach
- Start with the first run and set both run lengths to one.
- Scan the string from left to right.
- If the current character matches the previous one, extend the current run.
- Otherwise, add the smaller run length to the answer, then shift the current run into the previous-run count and start a new run.
- Add the final pair’s contribution after the scan.
class Solution:
def countBinarySubstrings(self, s: str) -> int:
previous_run = 0
current_run = 1
total = 0
for i in range(1, len(s)):
if s[i] == s[i - 1]:
current_run += 1
else:
total += min(previous_run, current_run)
previous_run = current_run
current_run = 1
# Account for the final pair of neighboring runs.
total += min(previous_run, current_run)
return total
Complexity:
- Time: O(n), where n is the string length; each character is processed once.
- Space: O(1), using only a few counters.
Common follow-ups
- How would you return the actual substrings? Track each run boundary and enumerate the valid lengths, though output size can be large.
- What if the input alphabet has more than two characters? The equal-sized neighboring-run rule applies to adjacent runs of two different characters; clarify the exact validity condition first.
- How would you handle a stream of characters? Maintain the two run counts and update the total when a run transition is observed; finalize the last pair when the stream ends.