leetcode-696-easy

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

思路一：先预处理字符串，统计 0 和 1 出现的次数，结果放入到一个数组中，有个统计的数组可以求结果，如下

对于字符串 "00110011"
生成数组 [0, 2, 0, 2, 0, 2, 0, 2]
观察数组可知，对于不为 0 的前后两个统计数字，总数=Math.min(first, second)

public int countBinarySubstrings(String s) {
    char[] chars = s.toCharArray();
    int[] arr = new int[chars.length];

    int count = 1;
    for (int i = 1; i < chars.length; i++) {
        if (chars[i] == chars[i - 1]) {
            count++;
        } else {
            arr[i - 1] = count;
            count = 1;
        }
    }

    if (arr[arr.length - 1] == 0) {
        arr[arr.length - 1] = count;
    }

    int first = -1;
    count = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 0) continue;

        if (first == -1) {
            first = i;
        } else {
            count += Math.min(arr[first], arr[i]);
            first = i;
        }
    }

    return count;
}