Solution: Count Binary Substrings

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #696 (Easy): Count Binary Substrings

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

---

Examples:

Example 1:
Input:	"00110011"
Output:	6
Explanation:	There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:
Input:	"10101"
Output:	4
Explanation:	There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

---

Constraints:

• s.length will be between 1 and 50,000.
• s will only consist of "0" or "1" characters.

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Since the 0's and 1's have to be grouped consecutively, we only have to be concerned with the most recent two groups (curr, prev) at any time as we iterate through the input string (s). Since each addition to our answer (ans) must therefore be centered on the "edge" between the two groups, we should be able to count multiple increases to ans at the same time.

For example, if we find a group that is "0001111", then we know that we've found multiple answer counts centered on the "01". Each additional extra character on both sides will be an extra answer, which means that "0011" and "000111" are also answers. In other words, the number that we should add to ans is equal to min(zeros, ones), or 3 in this example.

So we can now iterate through s, keeping track of the curr and prev groups, and when we find the end of a group, we can calculate our addition to ans and then swap the two variables while resetting curr to 1.

Since we're going to be comparing s[i] to s[i-1] to see if the character has changed, we'll need to start our iteration with i = 1 which means we should define a starting value for curr of 1. Also, since the end of s is technically the end of a group, we should add another min(curr, prev) onto ans before we return ans, as it won't be accounted for in the iteration through s.

• Time Complexity: O(N) where N is the length of s
• Space Complexity: O(1)

---

Implementation:

There are only minor differences in the code for all four languages.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var countBinarySubstrings = function(s) {
    let curr = 1, prev = 0, ans = 0
    for (let i = 1; i < s.length; i++)
        if (s[i] === s[i-1]) curr++
        else ans += Math.min(curr, prev), prev = curr, curr = 1
    return ans + Math.min(curr, prev)
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        curr, prev, ans = 1, 0, 0
        for i in range(1, len(s)):
            if s[i] == s[i-1]: curr += 1
            else:
                ans += min(curr, prev)
                prev, curr = curr, 1
        return ans + min(curr, prev)

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int countBinarySubstrings(String s) {
        int curr = 1, prev = 0, ans = 0;
        for (int i = 1; i < s.length(); i++)
            if (s.charAt(i) == s.charAt(i-1)) curr++;
            else {
                ans += Math.min(curr, prev);
                prev = curr;
                curr = 1;
            }
        return ans + Math.min(curr, prev);
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int countBinarySubstrings(string s) {
        int curr = 1, prev = 0, ans = 0;
        for (int i = 1; i < s.length(); i++)
            if (s[i] == s[i-1]) curr++;
            else ans += min(curr, prev), prev = curr, curr = 1;
        return ans + min(curr, prev);
    }
};

Comments

[malikmoss]

I'm still confused as to why we wouldn't start iterating at index 0. Wouldn't that be the first index to start from while comparing it to s[i] - 1? But I appreciate your explanation and solutions!

[seanpgallivan]

It's because we're comparing s[i] to s[i-1], not s[i] - 1. At i = 0, s[i-1] would be undefined, so we can't find a match until i = 1.

Thinking about it a different way, any matching substring has to be of even length (since it has an equal amount of 0's and 1's), so the first possible matching substring is when i = 1.

[malikmoss]

It just clicked. Thanks alot!

[seanpgallivan]

You're welcome!