Leetcode2272:最大波动的子字符串
题目描述:
字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
给你一个字符串 s
,它只包含小写英文字母。请你返回 s
里所有 子字符串的 最大波动 值。
子字符串 是一个字符串的一段连续字符序列。
代码思路:
- 预处理字符位置:首先统计每个字符在字符串中的所有出现位置,并在末尾添加一个哨兵值(字符串长度n),便于处理边界情况。
- 遍历字符对:对于每个字符对(M, m),使用双指针遍历它们的出现位置列表,动态调整窗口以最大化M的出现次数,同时最小化m的出现次数。
- 动态调整窗口:
- 当M的当前位置小于m的当前位置时,扩展窗口右端以增加M的计数。
- 反之,扩展窗口右端以增加m的计数。
- 当m的计数超过1时,收缩窗口左端以减少m的计数,确保m的计数不超过1。
- 计算波动值:在每次调整窗口后,若m的计数大于0,则计算当前窗口的波动值并更新全局最大值。
代码实现:
class Solution:
def largestVariance(self, s: str) -> int:
n = len(s)
table = defaultdict(list)
for i, c in enumerate(s):
table[c].append(i)
for t in table.values():
t.append(n) # 加一个额外结尾,方便遍历
result = 0
for M in table.keys():
Mq = table[M]
for m in table.keys():
if M == m: continue
mq = table[m]
Mleft = Mright = 0
mleft = mright = 0
Mc = mc = 0
while Mq[Mright] != mq[mright]: # 都到达最后时都是 n
if Mq[Mright] < mq[mright]:
Mright += 1
Mc += 1
else:
mright += 1
mc += 1
while mc > 1:
# 最左侧直接就是一个更少的
if mq[mleft] < Mq[Mleft]:
mleft += 1
mc -= 1
# 最左侧弹出一个多的一个少的
else:
mleft += 1
Mleft += 1
mc -= 1
Mc -= 1
if mc:
result = max(result, Mc - mc)
return result