Count Binary Substrings

JCSU Unit 15 Problem Set 1 (Click for link to problem statements)

Problem Highlights

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

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 is the goal of the problem?
  • Count the number of substrings in the binary string s that have an equal number of 0’s and 1’s grouped consecutively.
• Are there constraints on input?
  • The string consists only of 0 and 1.

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

EDGE CASE
Input:
s = “10101”
Output:
4
Explanation:
Substrings: “10”, “01”, “10”, “01”.

EDGE CASE
Input:
s = “1111”
Output:
0
Explanation:
No valid substrings because there are no consecutive groups of 0’s and 1’s.

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 counting consecutive group substrings, we want to consider the following approaches:

• Sliding Window Approach: Track lengths of consecutive groups of 0’s and 1’s.
• Greedy Method: Use two counters to compare current and previous group lengths.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Traverse the string and calculate lengths of consecutive groups of 0’s and 1’s. Add the minimum of the previous and current group lengths to the count.

Steps:

1. Initialize variables:
   • prev_group_len to track the length of the previous group of characters.
   • curr_group_len to track the length of the current group of characters.
   • count to store the total number of valid substrings.
2. Traverse the string starting from the second character:
   • If the current character matches the previous one, increase curr_group_len.
   • Otherwise:
     • Add the minimum of prev_group_len and curr_group_len to count.
     • Update prev_group_len to curr_group_len.
     • Reset curr_group_len to 1.
3. Add the last pair of groups to count.
4. Return the total count.

4: I-mplement

Implement the code to solve the algorithm.

def count_binary_substrings(s):
    # Initialize variables to store the lengths of consecutive groups
    prev_group_len = 0
    curr_group_len = 1
    count = 0

    # Traverse the string to calculate the lengths of consecutive groups of '0's and '1's
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:  # If the current character matches the previous one, increase the current group length
            curr_group_len += 1
        else:
            # If characters change, add the minimum of the previous and current group lengths to the count
            count += min(prev_group_len, curr_group_len)
            prev_group_len = curr_group_len  # Update the previous group length
            curr_group_len = 1  # Reset the current group length

    # Add the last pair of groups to the count
    count += min(prev_group_len, curr_group_len)

    return count

5: R-eview

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

Example 1:

• Input: s = “00110011”
• Expected Output: 6
• Observed Output: 6

Example 2:

• Input: s = “10101”
• Expected Output: 4
• Observed Output: 4

Example 3:

• Input: s = “1111”
• Expected Output: 0
• Observed Output: 0

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 once.
• Space Complexity: O(1) because we use constant additional space for variables.