696. Count Binary Substrings LeetCode Solution

In this guide, you will get 696. Count Binary Substrings LeetCode Solution with the best time and space complexity. The solution to Count Binary Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Binary Substrings solution in C++
Count Binary Substrings solution in Java
Count Binary Substrings solution in Python
Additional Resources

696. Count Binary Substrings LeetCode Solution image

Problem Statement of 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 <= 105
s[i] is either '0' or '1'.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

696. Count Binary Substrings LeetCode Solution in C++

class Solution {
 public:
  int countBinarySubstrings(string s) {
    int ans = 0;
    int prevEquals = 0;
    int currEquals = 1;

    for (int i = 0; i + 1 < s.length(); ++i)
      if (s[i] == s[i + 1])
        ++currEquals;
      else {
        ans += min(prevEquals, currEquals);
        prevEquals = currEquals;
        currEquals = 1;
      }

    return ans + min(prevEquals, currEquals);
  }
};
/* code provided by PROGIEZ */

696. Count Binary Substrings LeetCode Solution in Java

class Solution {
  public int countBinarySubstrings(String s) {
    int ans = 0;
    int prevEquals = 0;
    int currEquals = 1;

    for (int i = 0; i + 1 < s.length(); ++i)
      if (s.charAt(i) == s.charAt(i + 1))
        ++currEquals;
      else {
        ans += Math.min(prevEquals, currEquals);
        prevEquals = currEquals;
        currEquals = 1;
      }

    return ans + Math.min(prevEquals, currEquals);
  }
}
// code provided by PROGIEZ

696. Count Binary Substrings LeetCode Solution in Python

class Solution:
  def countBinarySubstrings(self, s: str) -> int:
    ans = 0
    prevCount = 0
    equals = 1

    for i in range(len(s) - 1):
      if s[i] == s[i + 1]:
        equals += 1
      else:
        ans += min(prevCount, equals)
        prevCount = equals
        equals = 1

    return ans + min(prevCount, equals)
 # code by PROGIEZ