当前位置: 首页 > article >正文

Leetcode2272:最大波动的子字符串

题目描述:

字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。

给你一个字符串 s ,它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。

子字符串 是一个字符串的一段连续字符序列。

代码思路:

  1. 预处理字符位置:首先统计每个字符在字符串中的所有出现位置,并在末尾添加一个哨兵值(字符串长度n),便于处理边界情况。
  2. 遍历字符对:对于每个字符对(M, m),使用双指针遍历它们的出现位置列表,动态调整窗口以最大化M的出现次数,同时最小化m的出现次数。
  3. 动态调整窗口
    • 当M的当前位置小于m的当前位置时,扩展窗口右端以增加M的计数。
    • 反之,扩展窗口右端以增加m的计数。
    • 当m的计数超过1时,收缩窗口左端以减少m的计数,确保m的计数不超过1。
  4. 计算波动值:在每次调整窗口后,若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

 


http://www.kler.cn/a/588079.html

相关文章:

  • 文档搜索引擎
  • Gluten 项目贡献指南
  • 行为模式---模版模式
  • S32K144入门笔记(十):TRGMUX的初始化
  • 区块链知识点2
  • 3.水中看月
  • IP 地址
  • 一级运动员最小几岁·棒球1号位
  • 使用OpenResty(基于Nginx和Lua)优化Web服务性能
  • k8s系统学习路径
  • C语言之 条件编译和预处理指令
  • ospf单区域
  • 【MySQL】多表查询(笛卡尔积现象,联合查询、内连接、左外连接、右外连接、子查询)-通过练习快速掌握法
  • 【leetcode hot 100 108】将有序数组转换为二叉搜索树
  • 英语面试常见问题
  • 前缀和算法第一弹(一维前缀和和二维前缀和)
  • 【环境配置】windows下vscode下无法激活conda环境、创建虚拟环境报错
  • 算法题刷题方法记录(蓝桥杯、Leetcode)
  • Spring MVC拦截器中的责任链模式深度解析
  • 深度探索DeepSeek部署的安全底线