DEV Community

Cover image for Solution: Count Binary Substrings
seanpgallivan
seanpgallivan

Posted on

31 3

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)
};
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
};
Enter fullscreen mode Exit fullscreen mode

Agent.ai Challenge image

Congrats to the Agent.ai Challenge Winners πŸ†

The wait is over! We are excited to announce the winners of the Agent.ai Challenge.

From meal planners to fundraising automators to comprehensive stock analysts, our team of judges hung out with a lot of agents and had a lot to deliberate over. There were so many creative and innovative submissions, it is always so difficult to select our winners.

Read more β†’

Top comments (4)

Collapse
 
malikmoss profile image
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!

Collapse
 
seanpgallivan profile image
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.

Collapse
 
malikmoss profile image
malikmoss β€’

It just clicked. Thanks alot!

Thread Thread
 
seanpgallivan profile image
seanpgallivan β€’

You're welcome!

πŸ‘‹ Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay