Count Binary Substring - codepath/compsci_guides GitHub Wiki

Unit 12 Session 2 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Strings, Grouping, Sliding Window

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What does it mean for characters to be grouped consecutively?

  • All the 0's in a substring must appear together, followed by all the 1's (or vice versa).

• Are overlapping substrings counted?

  • Yes, every valid occurrence is counted.

HAPPY CASE
Input: s = "00110011"
Output: 6
Explanation: Substrings are "0011", "01", "1100", "10", "0011", "01".

Input: s = "10101"
Output: 4
Explanation: Substrings are "10", "01", "10", "01".

EDGE CASE
Input: s = "0000"
Output: 0
Explanation: No valid substrings as there are no consecutive 1's.

Input: s = ""
Output: 0
Explanation: An empty string has no substrings.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For String Grouping/Sliding Window problems, we want to consider the following approaches:

• Grouping Counts: Use a list to store consecutive counts of 0's and 1's.
• Adjacent Comparison: Compare adjacent groups to determine valid substrings.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the string and group consecutive 0's and 1's. Then, compare adjacent groups to calculate the number of valid substrings.

1) Initialize an empty list `groups` to store the counts of consecutive characters.
2) Use a variable `count` to track the length of consecutive `0`'s or `1`'s.
3) Traverse the string, updating `count` whenever the current character matches the previous one.
4) When a different character is encountered, store `count` in `groups` and reset `count` to 1.
5) After the loop, add the last count to `groups`.
6) Iterate through `groups` and calculate the sum of the minimum of every two consecutive group counts.
7) Return the total as the result.

⚠️ Common Mistakes

• Forgetting to add the last group to the list.
• Not handling strings with only 0's or 1's properly.

4: I-mplement

Implement the code to solve the algorithm.

def count_binary_substrings(s):
    groups = []
    count = 1
    
    # Count consecutive 0's and 1's
    for i in range(1, len(s)):
        if s[i] != s[i - 1]:
            groups.append(count)
            count = 1
        else:
            count += 1
    groups.append(count)
    
    # Compare adjacent groups
    result = 0
    for i in range(1, len(groups)):
        result += min(groups[i - 1], groups[i])
    
    return result

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: s = "00110011"

  • Groups: [2, 2, 2, 2]
  • Adjacent comparisons: min(2, 2) + min(2, 2) + min(2, 2) = 6
  • Output: 6

• Input: s = "10101"

  • Groups: [1, 1, 1, 1, 1]
  • Adjacent comparisons: min(1, 1) + min(1, 1) + min(1, 1) + min(1, 1) = 4
  • Output: 4

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the input string.

• Time Complexity: O(N) because we traverse the string twice—once to count consecutive groups and once to sum valid substrings.
• Space Complexity: O(N) because we store the counts of consecutive groups in a list.