题目描述

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.

Example 1:

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.

Example 2:

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

Note:

  • s.length will be between 1 and 50,000.
  • s will only consist of "0" or "1" characters.

解法一

思路

这题乍看起来很复杂,但实际有一个很容易的解法。注意到题目条件,符合要求的子串需要“有相同数目的0和1”而且“0和1都是连续的”,举例来说,对于00110011,满足条件的子串只有010011101100010011,而00110011不满足条件。

既然如此,对于“当前位置”的数字来说,就只需要关注其“紧邻之前”有多少个相同数字,以及有多少个不同数字就好了。比如,当处理到00110时,对于最后一个0来说,只需要关注前面有没有1个1,这时10就是满足条件的子串;而当处理到001100时,对于最后一个0来说,它是第2个0,而其前面有2个1,这时1100就是满足条件的子串;再当处理到0011000时,对于最后一个0来说,它是第3个0,而其前面只有2个1,所以子串11000不满足条件。

综上,我们可以在处理每个数字时,记录下“紧邻之前”的不相同数字的个数,并进行比较,判断以此结尾的子串是否满足条件。这里来个更完整的例子。

  001110010    prev = 0    cur = 0
 0 01110010    prev = 0    cur = 1
0 0 1110010    prev = 0    cur = 2
00 1 110010    prev = 2    cur = 1    01
001 1 10010    prev = 2    cur = 2    0011
0011 1 0010    prev = 2    cur = 3
00111 0 010    prev = 3    cur = 1    10
001110 0 10    prev = 3    cur = 2    1100
0011100 1 0    prev = 2    cur = 1    01
00111001 0     prev = 1    cur = 1    10

Python

class Solution:
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = 0
        prev_length = 0
        cur_length = 1
        for i in range(1, len(s)):
            if (s[i] == s[i - 1]):
                cur_length += 1
            else:
                prev_length = cur_length
                cur_length = 1
            if prev_length >= cur_length:
                result += 1
        return result

Java

class Solution {
    public int countBinarySubstrings(String s) {
        int result = 0;
        int prevLength = 0;
        int curLength = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                curLength++;
            } else {
                prevLength = curLength;
                curLength = 1;
            }
            if (prevLength >= curLength) {
                result++;
            }
        }
        return result;
    }
}

C++

class Solution {
public:
    int countBinarySubstrings(string s) {
        int result = 0;
        int prevLength = 0;
        int curLength = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == s[i - 1]) {
                curLength++;
            } else {
                prevLength = curLength;
                curLength = 1;
            }
            if (prevLength >= curLength) {
                result++;
            }
        }
        return result;
    }
};