Count Binary Substrings

• LeetCode: Count Binary Substrings

• Problem:

Give 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.

• Note:

1. s.length will be between 1 and 50,000.

2. s will only consist of "0" or "1" characters.

• Examples:

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.

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

• Analysis:

The long binary substring would contains all short binary substring.

Use two pointers to find the long binary substrings and counts the number of one and zero.

For every long binary substring, the min(oneCnt, zeroCnt) is the all the number of short binary substrings for a long binary substring. 

For examples,

     string = "00111", the long substring is 00111 while count of 0 is 2 and count of 1 is 3. 

     The number of all binary substrings are min(2, 3) = 2, 0011, 01

• Code - Java:

class Solution {
    public int countBinarySubstrings(String s) {
        int len = s.length();
        int count = 0;
        int zero = 0;
        int one = 0;
        int zeroCnt = 0;
        int oneCnt = 0;
        while (true) {
            while (zero < len && s.charAt(zero) == '0') {
                zero++;
            }
            zeroCnt = zero - one;
            count += Math.min(zeroCnt, oneCnt);
            if (zero == len) {
                break;
            }
            oneCnt = 0;
            one = zero;
            while (one < len && s.charAt(one) == '1') {
                one++;
            }
            oneCnt = one - zero;
            count += Math.min(zeroCnt, oneCnt);
            if (one == len) {
                break;
            }
            zero = one;
            zeroCnt = 0;
        }
        return count;
    }
}

• Code - C++:

class Solution {
public:
    int countBinarySubstrings(string s) {
        int len = s.length();
        int count = 0;
        int zero = 0;
        int one = 0;
        int zeroCnt = 0;
        int oneCnt = 0;
        while (true) {
            while (zero < len && s[zero] == '0') {
                zero++;
            }
            zeroCnt = zero - one;
            count += min(zeroCnt, oneCnt);
            if (zero == len) {
                break;
            }
            oneCnt = 0;
            one = zero;
            while (one < len && s[one] == '1') {
                one++;
            }
            oneCnt = one - zero;
            count += min(zeroCnt, oneCnt);
            if (one == len) {
                break;
            }
            zero = one;
            zeroCnt = 0;
        }
        return count;
    }
};

• Code - Python:

class Solution(object):
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        sLen = len(s)
        count, zero, one, zeroCnt, oneCnt = 0, 0, 0, 0, 0
        while True:
            while zero < sLen and s[zero] == '0':
                zero += 1
            zeroCnt = zero - one
            count += min(zeroCnt, oneCnt)
            if zero == sLen:
                break
            oneCnt = 0
            one = zero
            while one < sLen and s[one] == '1':
                one += 1
            oneCnt = one - zero
            count += min(zeroCnt, oneCnt)
            if one == sLen:
                break
            zero = one
            zeroCnt = 0
        return count

• Time Complexity: O(N), N is the length of the input string

• Space Complexity: O(1)