*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:*

*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:*

*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:*

*Constraints:*

`s.length`

will be between`1`

and`50,000`

.`s`

will only consist of "`0`

" or "`1`

" characters.

####
*Idea:*

*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:*

*Implementation:*

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

####
*Javascript Code:*

*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:*

*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:*

*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:*

*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);
}
};
```

## Discussion (4)

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!

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.

It just clicked. Thanks alot!

You're welcome!