2953. 统计完全子字符串

跳转: 2953. 统计完全子字符串

学习: 题解

问题:

给你一个字符串 word 和一个整数 k 。

如果 word 的一个子字符串 s 满足以下条件，我们称它是 完全字符串：

s 中每个字符恰好出现 k 次。
相邻字符在字母表中的顺序至多相差 2 。也就是说，s 中两个相邻字符 c1 和 c2 ，它们在字母表中的位置相差至多为 2 。

请你返回 word 中完全子字符串的数目。

子字符串 指的是一个字符串中一段连续非空的字符序列。

思路:

从k长的窗口开始,2k,3k长依此遍历求字典值全是k的情况计数不难想
因为相邻差至多为2，所以遍历整个数组要维护窗口相邻差最值
用分组循环从边界切开分段求能简化计算同时降低复杂度

一共26个小写字母，所以哪怕长度大于26 * k也不需要再遍历
每个字符k次除了直接遍历一遍字典还可以维护字典中值为k的数量

复杂度:

时间复杂度: $O (26 * 4 * n)$
空间复杂度: $O (26)$

代码:

class Solution:def countCompleteSubstrings(self, word: str, k: int) -> int:def f(s:list) -> int:ans = 0for size in range(1,27):    # 26个字母，所以最多不会超过26，后面的都不用算j = size * kif j > len(s):breakcnt = Counter(s[:j])count = 0for i in cnt.values():if i == k:count += 1if count == size:   # 因为和是j，所以统计cnt里的k对上size即可ans += 1for i,ch in enumerate(s[j:]):if cnt[ch] == k:count -= 1cnt[ch] = cnt.get(ch,0) + 1if cnt[ch] == k:count += 1if cnt[s[i]] == k:count -= 1cnt[s[i]] -= 1if cnt[s[i]] == k:count += 1if count == size:ans += 1return ansi = ans = 0n = len(word)while i in range(n):    # 分组循环start = ii += 1while i < n and abs(ord(word[i])-ord(word[i - 1])) <= 2:i += 1ans += f(word[start:i])return ans

1016. 子串能表示从 1 到 N 数字的二进制串

跳转: 1016. 子串能表示从 1 到 N 数字的二进制串

学习: 题解

问题:

给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。

子字符串 是字符串中连续的字符序列。

思路:

对于去除前导0的二进制串，更长的串集合整体右移一位完全可以覆盖更短的串
于是可以用滑动窗口遍历最长的串集合
但由于n不一定是2的幂-1或-2，即最长的串集合一般不全，所以确保不漏，除了最长的次长的二进制串也要遍历

即以n的二进制长-1为k，在s上求 k 长和 k+1 长的滑动窗口

区间 $2^k,n]$ 内的二进制数的长度均为 $k + 1$ ，这有 $n−2^k+1$ 个，所以应满足 $m≥k+1+(n−2^k+1−1)=n−2^k+k+1$ 。
区间 $2^{k−1},2^k−1]$ 内的二进制数的长度均为 k，这有 $2^{k−1}$ 个，所以应满足 $m≥k+(2^{k−1}−1)=2^{k−1}+k−1$ 。

复杂度:

时间复杂度: $O (m)$
空间复杂度: $O (min (m, n))$

代码:

# class Solution:
#     def queryString(self, s: str, n: int) -> bool:
#         set_ = set()
#         s = list(map(int,s))
#         for i,num in enumerate(s):
#             if num == 0: continue
#             j = i + 1
#             while num <= n:
#                 set_.add(num)
#                 if j == len(s): break
#                 num = num << 1 | s[j]
#                 j += 1
#         return len(set_) == nclass Solution:def queryString(self, s: str, n: int) -> bool:if n == 1:return "1" in sm = len(s)k = n.bit_length() - 1if m < max(k + 1 + (n - (1 << k)), k + (1 << k - 1) - 1):return Falsedef check(k: int, lower: int, upper: int) -> bool:if lower > upper:return Trueif k == 1:return "1" in sseen = set()bits = list(map(int, s[k - 1 :]))num = int(s[: k - 1], 2)mask = (1 << k - 1) - 1# 滑动窗口只找k长的二进制值即可for i in bits:num = ((num & mask) << 1) + iif lower <= num <= upper:seen.add(num)return len(seen) == upper - lower + 1# return check(k + 1, 1 << k, n) and check(k, 1 << k - 1, (1 << k) - 1)# 可以进一步缩小范围，不必计算全部的2^{k-1}到2^k-1,因为会和2^k到n有重复# return check(k + 1, 1 << k, n) and check(k, (n >> 1) + 1, (1 << k) - 1)# 实测用 n//2 性能更优return check(k + 1, 1 << k, n) and check(k, n // 2 + 1, (1 << k) - 1)