Solution: Count Binary Substrings
Tags: algorithms, javascript, java, python
Published: 2021-04-23 08:06:20

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/count-binary-substrings/discuss/1172553).*

---

#### [Leetcode Problem #696 (*Easy*): Count Binary Substrings](https://leetcode.com/problems/count-binary-substrings/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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".<br>Notice that some of these substrings repeat and are counted the number of times they occur.<br>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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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);
    }
};
```