696. Count Binary Substrings

EasyTwo PointersString
Leetcode Link

Problem Description

The problem asks for the number of non-empty substrings in a given binary string s, where these substrings have an equal number of 0's and 1's and the 0's and 1's are grouped consecutively. That means in every valid substring, all the 0's will be together and all the 1's will be together, with no mixing or interleaving. For example, the substring "0011" is valid as it has two 0's followed by two 1's, but "0101" is not valid as here 0's and 1's are not grouped together. It's also necessary to count multiple occurrences of the same substrings separately if they appear in different positions in the string s.

Intuition

The intuition behind the solution approach is to break the problem into smaller, more manageable pieces that we can count efficiently. We want to count substrings where 0's and 1's are grouped together, which means we only need to focus on transitions from 0 to 1 or from 1 to 0. Whenever such a transition is found, the number of possible substrings is the minimum of the number of 0's and 1's around this transition point, because the substring must end when a different character starts.

Here's the approach in more detail:

  • We first iterate through string s to create a list t that stores the lengths of consecutive 0's or 1's (we can call each consecutive sequence a "block"). For example, if s is "00111011", the list will be [2, 3, 1, 2] which corresponds to "00", "111", "0", and "11".
  • Next, we look for consecutive blocks where a 0 block is followed by a 1 block, or vice versa, and add the minimum length of these two blocks to our answer. This is because, at each transition, the number of valid substrings is limited by the shorter block. This step counts the valid substrings that occur around the transitions we identified.
  • We iterate over the list t and add up the minimum values between adjacent blocks to get the total count of substrings.

The advantage of this method is that we convert the problem from having to consider all possible substrings (which would be very inefficient) to considering only the transitions between different characters, which greatly reduces the number of possibilities we need to examine.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is a min heap?

Solution Approach

The implementation of the solution utilizes a simple array (list in Python) to keep track of the counts of consecutive characters and then uses a single pass to calculate the number of valid substrings.

Here's the step-by-step explanation of the algorithm:

  1. Initialize an index i to start from the beginning of the string s and determine the length n of the string for boundary conditions. Also, prepare an empty list t to store the lengths of consecutive characters.

  2. Use a while loop to iterate over the string:

    • The inner while loop counts consecutive characters that are the same and increments the count cnt. The condition s[i + 1] == s[i] checks for consecutive similar characters.
    • This count is then appended to the list t after the end of the consecutive characters is reached, and the outer loop is moved to the next character that is different.

  3. After the loop ends, you have a list t that contains the counts of consecutive 0's or 1's. For the given string "00111011", t would be [2, 3, 1, 2].

  4. Now, initialize a variable ans to 0. This will hold the final count of valid substrings.

  5. Iterate over the list t using a for loop starting from index 1 since we want to compare each block with its previous block:

    • For each pair of consecutive blocks, add the minimum of the two block lengths to ans. The expression min(t[i - 1], t[i]) does exactly that, considering the current and previous block count.

  6. Finally, return ans, which now contains the total number of valid substrings.

The algorithm effectively uses a grouping-and-counting technique, converting the input string into a list of counts that represents the "compressibility" of the data. This allows for an efficient counting of the substrings in a second pass without the need for nested loops and without having to check each possible substring within the original string.

This code has a linear time complexity, O(n), because it only requires two passes over the input: one to create the count list and one to compute the result from the count list. The space complexity is also linear, O(n), because it requires additional space proportional to the size of the input to store the count list.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's walk through an example to illustrate the solution approach with the binary string s = "00110011".

  1. Initialize index and list: We start with an index i = 0, and an empty list t = [].

  2. Count consecutive characters:

    • The first two characters are 0s. The inner while loop counts these two 0s and we append 2 to the list t. Now, t = [2].
    • The next three characters are 1s. We count these and append 3 to t. Now, t = [2, 3].
    • After that, we have two 0s, so we append 2 to t. Now, t = [2, 3, 2].
    • Finally, we count two 1s and t becomes [2, 3, 2, 2].

  3. List t represents blocks: After this step, for the string "00110011", the list t is [2, 3, 2, 2]. Each number represents a block of consecutive characters.

  4. Initialize answer variable: Set ans = 0.

  5. Iterate over the list t and count substrings:

    • We compare the first and second blocks: 2 and 3. The minimum is 2, so we add 2 to ans.
    • Next, we compare the second and third blocks: 3 and 2. The minimum is 2, add 2 to ans.
    • Then we compare the third and fourth blocks: 2 and 2. The minimum is 2, add 2 to ans.
    • After iterating, ans is 2 + 2 + 2 = 6.

  6. Result: The total number of non-empty substrings that have an equal number of 0s and 1s and are grouped consecutively is 6.

Valid substrings based on the given example are "0011", "01", "1100", "10", "0011", and "01" at different positions in the string. The approach successfully simplifies the problem by focusing on the transitions from 0 to 1 or from 1 to 0 and uses the concept of counting the minimum length of consecutive blocks to determine valid grouped substrings.

Solution Implementation

1class Solution:
2    def countBinarySubstrings(self, s: str) -> int:
3        # Initialize the index and get the length of the input string
4        index, length = 0, len(s)
5        # This list will store the counts of consecutive '0's or '1's
6        group_counts = []
7      
8        # Loop through the input string to create group counts
9        while index < length:
10            count = 1
11            # If the next character is the same, increment the count
12            while index + 1 < length and s[index + 1] == s[index]:
13                count += 1
14                index += 1
15            # Append the count of the group to the list
16            group_counts.append(count)
17            index += 1
18      
19        # Initialize the answer variable to store the total count
20        answer = 0
21        # Iterate over the group counts and add the minimum count of
22        # adjacent groups to the answer since they can form binary substrings
23        for i in range(1, len(group_counts)):
24            answer += min(group_counts[i - 1], group_counts[i])
25      
26        # Return the total count of binary substrings
27        return answer
28
1class Solution {
2    public int countBinarySubstrings(String s) {
3        // Initialize the current index 'currentIndex' which is used to traverse the string
4        int currentIndex = 0;
5        // The length of the input string 's'
6        int length = s.length();
7        // A list to store the consecutive character counts
8        List<Integer> groups = new ArrayList<>();
9      
10        // Traverse the entire string
11        while (currentIndex < length) {
12            // Starting count is 1 since we're looking at one character initially
13            int count = 1;
14            // Check if the next character is the same as the current one
15            while (currentIndex + 1 < length && s.charAt(currentIndex + 1) == s.charAt(currentIndex)) {
16                currentIndex++;
17                count++;
18            }
19            // Add the count to the list of group counts
20            groups.add(count);
21            // Move to the next character
22            currentIndex++;
23        }
24      
25        // Initialize 'totalSubstrings' to count the number of valid binary substrings
26        int totalSubstrings = 0;
27        // Iterate through the list of group counts
28        for (int i = 1; i < groups.size(); i++) {
29            // Add the minimum count of adjacent groups since that is the maximum number of
30            // valid substrings we can get from those two groups
31            totalSubstrings += Math.min(groups.get(i - 1), groups.get(i));
32        }
33      
34        // Return the total number of valid binary substrings
35        return totalSubstrings;
36    }
37}
38
1class Solution {
2public:
3    int countBinarySubstrings(string s) {
4        int currentIndex = 0, stringSize = s.size(); // Initialize variables for the current index and the size of the string.
5        vector<int> groupLengths; // This vector will hold the lengths of consecutive groups of '0's or '1's.
6
7        // Process the input string to populate groupLengths with the lengths of consecutive groups.
8        while (currentIndex < stringSize) {
9            int count = 1; // Start with a count of 1 for the current character.
10            // Count consecutive characters that are the same.
11            while (currentIndex + 1 < stringSize && s[currentIndex + 1] == s[currentIndex]) {
12                ++count;
13                ++currentIndex;
14            }
15            groupLengths.push_back(count); // Add the count to the list of group lengths.
16            ++currentIndex; // Move to the next character (or next group of characters).
17        }
18
19        int answer = 0; // This will hold the total count of valid binary substrings.
20      
21        // Calculate the number of valid binary substrings using the lengths of groups.
22        for (int i = 1; i < groupLengths.size(); ++i) {
23            // The number of valid substrings for a pair of adjacent groups is the
24            // minimum of the lengths of those two groups.
25            answer += min(groupLengths[i - 1], groupLengths[i]);
26        }
27
28        return answer; // Return the total count of valid binary substrings.
29    }
30};
31
1// Counts the number of binary substrings with equal number of consecutive 0s and 1s.
2function countBinarySubstrings(s: string): number {
3    let currentIndex = 0, stringSize = s.length; // Initialize variables for the current index and the size of the string.
4    let groupLengths: number[] = []; // This array will hold the lengths of consecutive groups of '0's or '1's.
5
6    // Process the input string to populate groupLengths with the lengths of consecutive groups.
7    while (currentIndex < stringSize) {
8        let count = 1; // Start with a count of 1 for the current character.
9        // Count consecutive characters that are the same.
10        while (currentIndex + 1 < stringSize && s[currentIndex + 1] === s[currentIndex]) {
11            count++;
12            currentIndex++;
13        }
14        groupLengths.push(count); // Add the count to the list of group lengths.
15        currentIndex++; // Move to the next character (or next group of characters).
16    }
17
18    let answer = 0; // This will hold the total count of valid binary substrings.
19  
20    // Calculate the number of valid binary substrings using the lengths of groups.
21    for (let i = 1; i < groupLengths.length; i++) {
22        // The number of valid substrings for a pair of adjacent groups is the
23        // minimum of the lengths of those two groups.
24        answer += Math.min(groupLengths[i - 1], groupLengths[i]);
25    }
26
27    return answer; // Return the total count of valid binary substrings.
28}
29
Not Sure What to Study? Take the 2-min Quiz：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily determined by the two loops present in the algorithm. The first loop iterates over the string s to count consecutive characters and fill the array t with the lengths of these consecutive sequences. This loop has a complexity of O(n) where n is the length of the string s, because each character is visited at most twice.

The second loop goes through the array t (which has at most n elements if the string s is alternating between 0 and 1) calculating the number of valid binary substrings, which is also done in O(n) time because it processes each group once.

Therefore, the overall time complexity of the code is O(n) + O(n) = O(n).

Space Complexity

The space complexity is also determined by the array t. This array holds at most n elements in the worst-case scenario when the binary string alternates characters. Hence, the space complexity of the code is O(n) due to the storage requirements of the array t.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫