Algorithm
Problem Name: 696. Count Binary Substrings
Problem Link: https://leetcode.com/problems/count-binary-substrings/
Given a binary string s, return the number of non-empty 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.
Example 1:
Input: s = "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: s = "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
Constraints:
1 <= s.length <= 105s[i]is either'0'or'1'.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int countBinarySubstrings(string s) {
int count = 0;
for(int i = 0, j = 0; i < s.size(); j = i){
int a = 0, b = 0;
while(j < s.size() && s[j] == s[i]) j++, a++;
i = j;
while(j < s.size() && s[j] == s[i]) j++, b++;
count += min(a, b);
}
return count;
}
};
Input
s = "00110011"
Output
6
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int countBinarySubstrings(String s) {
int totalCount = 0;
int currCount = 0;
int oppositeCount = 0;
char currChar = s.charAt(0);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == currChar) {
currCount++;
} else {
totalCount += Math.min(currCount, oppositeCount);
oppositeCount = currCount;
currCount = 1;
currChar = s.charAt(i);
}
}
return totalCount + Math.min(currCount, oppositeCount);
}
}
Input
s = "00110011"
Output
6
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def countBinarySubstrings(self, s):
s = s.replace("01", "0#1").replace("10", "1#0").split("#")
return sum(min(len(s[i]), len(s[i - 1])) for i in range(1, len(s)))
Input
s = "10101"
Output
4
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0696_CountBinarySubstrings
{
public int CountBinarySubstrings(string s)
{
int curr = 1, prev = 0, result = 0;
for (int i = 1; i < s.Length; i++)
{
if (s[i] != s[i - 1])
{
result += Math.Min(curr, prev);
prev = curr;
curr = 1;
}
else
curr++;
}
return result + Math.Min(curr, prev);
}
}
}
Input
s = "10101"
Output
4