LeetCode 696. Count Binary Substrings

Question

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

Source: https://leetcode.com/problems/count-binary-substrings/

Solution

Represent the string as groups of continuous 1s and 0s. The question requires “substrings”, which greatly simplifies the solution since characters in a substring must be continuous in the original string.

// group
// Time Complexity: O(N), Space Complexity: O(N)
public int countBinarySubstrings(String s) {
    // parameter validation
    if (s == null || s.length() < 1) {
        return 0;
    }
    int len = s.length();
    int[] group = new int[len];
    int lastGroupIndex = 0;
    group[0] = 1;
    // get 0,1 distribution
    // [3, 2, 4, 1] for "1110011110"
    for (int i = 1; i < len; i++) {
        if (s.charAt(i - 1) != s.charAt(i)) {
            lastGroupIndex++;
            group[lastGroupIndex] = 1;
        } else {
            group[lastGroupIndex]++;
        }
    }
    int result = 0;
    for (int i = 1; i <= lastGroupIndex; i++) {
        result += Math.min(group[i - 1], group[i]);
    }
    return result;
}

// space optimized
// like Fibonacci sequence
// Time Complexity: O(N), Space Complexity: O(1)
public int countBinarySubstrings2(String s) {
    // parameter validation
    if (s == null || s.length() < 1) {
        return 0;
    }
    int len = s.length();
    int result = 0, lastGroupNum = 0, currGroupNum = 1;
    for (int i = 1; i < len; i++) {
        if (s.charAt(i - 1) != s.charAt(i)) {
          	// update result at the start of a new group
            result += Math.min(lastGroupNum, currGroupNum);
            lastGroupNum = currGroupNum;
            currGroupNum = 1;
        } else {
            currGroupNum++;
        }
    }
  	// handle corner case
    result += Math.min(lastGroupNum, currGroupNum);
    return result;
}