Leetcode2272最大波动的子字符串
目录
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