JZX轻语：简
LeetCode 2981 - 找出出现至少三次的最长特殊子字符串 I
发表于2024年05月29日
朴素的做法是使用双重循环，枚举并计数所有的的特殊子字符串(即所有字符相同，当遇到不一样的字符时终止内层循环)，但这样会超时。我们可以通过滑动窗口的方式节省遍历连续重复字符的时间，维护当前字符last_ch及其连续重复次数recessive_cnt，并使用二维数组ch_recessive_counts[i][j]维护第i个小写字母连续组成j次的子串计数。然后在每次循环最后，更新计数信息ch_recessive_counts[last_ch][j] += 1 (1 <= j <= recessive_cnt)。然后再更新最长且出现至少三次的子串即可。
class Solution:
def maximumLength(self, s: str) -> int:
ch_recessive_counts = [[0] * 51 for _ in range(26)]
last_ch = ''
recessive_cnt = 0
max_len = -1
for i, ch in enumerate(s):
if last_ch == ch:
recessive_cnt += 1
else:
last_ch = ch
recessive_cnt = 1
ch_index = ord(ch) - ord('a')
for j in range(1, recessive_cnt + 1):
ch_recessive_counts[ch_index][j] += 1
# 更新结果
if ch_recessive_counts[ch_index][j] >= 3 and j > max_len:
max_len = j
return max_len超时的版本：
class Solution:
def maximumLength(self, s: str) -> int:
cnt_map = defaultdict(int)
max_len = -1
for i, ch in enumerate(s):
for l in range(1, len(s) - i + 1):
if s[i + l - 1] != ch:
break
sub = s[i:i + l]
cnt_map[sub] += 1
if cnt_map[sub] >= 3 and len(sub) > max_len:
max_len = len(sub)
return max_len