696. 计数二进制子串

Tags: 字符串

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。重复出现的子串要计算它们出现的次数。

1. 最开始的思路首先没有注意到可以考虑重复子串的情况，且按照最直接的思路双重循环遍历字符串寻找满足条件的子串，时间复杂度达到，结果超出时间限制。
2. 参考官方题解，思路是依次计算整个字符串中的连续字符个数，保存在数组中，之后两两元素的遍历这个新数组，每次累加的个数是min(arr[i], arr[i+1])。此时的时间复杂度是O(n)，空间复杂度也是O(n)。

ch_cnt = []
last_ch = ''
for ch in s:
    if ch != last_ch:
        ch_cnt.append(1)
        last_ch = ch
    else:
        ch_cnt[-1] += 1

res = 0
for i in range(len(ch_cnt)-1):
    res += min(ch_cnt[i], ch_cnt[i+1])
return res

3. 注意到2中每次只需考虑邻接的两个连续字符子串的长度，因此可以省去存储整个字符串包含的连续字符子串的数组，只记录邻接的两个连续字符子串的长度进行比较计算答案，使得空间复杂度缩小至O(1)。

# 优化空间复杂度（以下代码是每遍历到一个新字符，就进行依次结果的判断）
last_cnt = 0
this_cnt = 1
last_ch = s[0]
res = 0
for i in range(1,len(s)):
    ch = s[i]
    if ch != last_ch:
        last_ch = ch
        last_cnt = this_cnt
        this_cnt = 1
        res += 1
    else:
        this_cnt += 1
        if this_cnt <= last_cnt:
            res += 1

return res

以上代码略显冗余，参考题解又对代码结构进一步优化：

# 每遍历完一个连续重复字符子串再进行结果的计算
i, res, last = 0, 0, 0
while i < len(s):
    ch = s[i]
    cnt = 0
    while i < len(s) and s[i] == ch:
        i += 1
        cnt += 1
    res += min(cnt, last)
    last = cnt
return res