696. Count Binary Substrings

Question

696. Count Binary Substrings

Example1

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.

Example2

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

Solution

题目大意:

给一个只有01组成的字符串,求子串数,子串必须满足

1. 0和1出现次数一样
2. 保证0连续1连续

思路:

参考下面参考链接的思路:

上一个连续子串长度记为preRunLength,当前连续子串长度记为curRunLength,res记为满足条件的子串数

Java实现:

public int countBinarySubstrings(String s) {
    int preRunLength = 0, curRunLength = 1, res = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) { // 当前字符与上一字符相同,表示当前连续子串未断
            curRunLength++; // 当前连续子串长度加1
        } else { // 当前字符与上一字符不同,表示当前连续子串结束
            preRunLength = curRunLength; // 当前连续子串长度变为上一个连续子串长度
            curRunLength = 1; // 当前连续子串长度为1
        }
        if (preRunLength >= curRunLength) res++; // 当前连续子串长度小于上一个连续子串长度就满足要求
    }
    return res;
}

Ref

Java-O(n)-Time-O(1)-Space