leetcode-696-Count-Binary-Substrings

发表于   |  

描述

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:

1
2
3
4
5
6
7
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:

1
2
3
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.

分析

题目的要求是子串有相同个数的1和0，并且1和0是连续的，所以例子里的00110011的子串 00110011不符合要求，根据特性，我们可以计算当前连续的个数，与之前计算的连续的个数比较，如果前面紧连的长度大于等于目前的长度，则为我们要找的子串。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countBinarySubstrings(String s) {
        int result = 0, previousLength = 0, currentLength = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1)) {
                currentLength++;
            } else {
                previousLength = currentLength;
                currentLength = 1;
            }
            if (previousLength >= currentLength) {
                result++;
            }
        }
        return result;
    }
}

相关问题

题目来源