问题描述
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.
问题分析
因为子串要求01总是连续的，所以对于{000…}{111…}这样有N个连续的0或者1来说，我们只需要找到中间的01，然后不断向两边延伸查找最大连续数量即可。如果中间10同理
代码如下:
初始解法
func countBinarySubstrings(s string) int {
ans := 0
for i := 0; i < len(s)-1; i++ {
// 如果接下来的子串为 01 或者 10
if (s[i] == '0' && s[i+1] == '1') || (s[i] == '1' && s[i+1] == '0') {
ans++
// 左右指针，向两边延伸查找；每找到一个，ans+1
l, r := i-1, i+2
for {
if l < 0 || r >= len(s) {
break
}
if s[l] != s[i] || s[r] != s[i+1] {
break
}
ans++
l--
r++
}
}
}
return ans
}
优化解法
初始解法时间复杂度较高，提交AC后，评论区优化版的解法如下：
对于{0000…}{1111…}这样的形式，假设有m个0，n个1；那么显然符合条件的子串数量为 min(m, n)。由此，我们可以定义2个变量：
prev: 表示上一个0或者1连续的数量
cur: 表示当前正在统计的0或者1的连续数量
如果当前元素与上一个元素相同，那么cur++即可；
如果不同，那么符合条件的子串数量加上 min(cur, prev)；并将prev更新为cur，而cur更新为1；进入下一轮判断
// optimized solution
func countBinarySubstringsV2(s string) int {
ans := 0
cur, prev := 1, 1
for i := 1; i < len(s); i++ {
if s[i] == s[i-1] {
cur++
} else {
ans += min(cur, prev)
prev = cur
cur = 1
}
}
return ans
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}