尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
分治题目:至少有 K 个重复字符的最长子串
文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题至少有 K 个重复字符的最长子串出处395. 至少有 K 个重复字符的最长子串难度6 级题目描述要求给定一个字符串s \texttt{s}s和一个整数k \texttt{k}k找到s \texttt{s}s中的每个字符出现次数都大于等于k \texttt{k}k的最长子串返回该子串的长度。示例示例 1输入s aaabb, k 3 \texttt{s aaabb, k 3}s aaabb, k 3输出3 \texttt{3}3解释最长子串为aaa \texttt{aaa}aaa其中‘a’ \texttt{a}‘a’重复了3 \texttt{3}3次。示例 2输入s ababbc, k 2 \texttt{s ababbc, k 2}s ababbc, k 2输出5 \texttt{5}5解释最长子串为ababb \texttt{ababb}ababb其中‘a’ \texttt{a}‘a’重复了2 \texttt{2}2次‘b’ \texttt{b}‘b’重复了3 \texttt{3}3次。数据范围1 ≤ s.length ≤ 10 4 \texttt{1} \le \texttt{s.length} \le \texttt{10}^\texttt{4}1≤s.length≤104s \texttt{s}s仅由小写英语字母组成1 ≤ k ≤ 10 5 \texttt{1} \le \texttt{k} \le \texttt{10}^\texttt{5}1≤k≤105解法思路和算法为方便表述将每个字符出现次数都大于等于k kk的子串称为「符合要求的子串」。为了得到字符串s ss中的符合要求的最长子串需要统计字符串s ss中的每个字符的出现次数并判断每个字符是否可能出现在符合要求的子串中。如果一个字符的出现次数小于k kk则该字符不可能出现在符合要求的子串中。每个出现次数小于k kk的字符所在的下标都是字符串s ss的一个分割下标将所有的分割下标按升序排序之后相邻两个分割下标之间的部分为一个子串继续对每个子串寻找符合要求的最长子串。将字符串s ss分割成多个子串之后对于每个子串可以使用相同的方法寻找符合要求的最长子串这是一个递归分治的过程。分治的终止条件是当前子串中的每个字符的出现次数都大于等于k kk此时符合要求的最长子串为当前子串。其余情况下每个出现次数小于k kk的字符所在的下标都是一个分割下标根据分割下标将当前子串分割成多个更小的子串之后对于每个更小的子串递归地寻找符合要求的最长子串。从字符串s ss开始递归分治对字符串s ss操作结束之后即可得到符合要求的最长子串的长度。实现方面有一处可以优化。如果当前子串被分割之后其中的一个更小的子串的长度小于等于已知的符合要求的最长子串的长度则该更小的子串中一定不存在长度更大的符合要求的子串因此不需要对该更小的子串寻找符合要求的最长子串。代码classSolution{publicintlongestSubstring(Strings,intk){returnlongestSubstring(s,0,s.length()-1,k);}publicintlongestSubstring(Strings,intstart,intend,intk){int[]countsnewint[26];for(intistart;iend;i){counts[s.charAt(i)-a];}ListIntegersplitIndicesnewArrayListInteger();for(intistart;iend;i){if(counts[s.charAt(i)-a]k){splitIndices.add(i);}}splitIndices.add(end1);if(splitIndices.size()1){returnend-start1;}intmaxLength0;intleft0;for(intsplitIndex:splitIndices){if(splitIndex-leftmaxLength){maxLengthMath.max(maxLength,longestSubstring(s,left,splitIndex-1,k));}leftsplitIndex1;}returnmaxLength;}}复杂度分析时间复杂度O ( n × ∣ Σ ∣ ) O(n \times |\Sigma|)O(n×∣Σ∣)其中n nn是字符串s ss的长度Σ \SigmaΣ是字符集这道题中Σ \SigmaΣ是全部小写英语字母∣ Σ ∣ 26 |\Sigma| 26∣Σ∣26。由于每次递归调用都会至少排除一个字母因此递归调用栈共有O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)层每一层需要O ( n ) O(n)O(n)的时间遍历字符串s ss一次因此时间复杂度是O ( n × ∣ Σ ∣ ) O(n \times |\Sigma|)O(n×∣Σ∣)。空间复杂度O ( ∣ Σ ∣ 2 ) O(|\Sigma|^2)O(∣Σ∣2)其中Σ \SigmaΣ是字符集这道题中Σ \SigmaΣ是全部小写英语字母∣ Σ ∣ 26 |\Sigma| 26∣Σ∣26。由于每次递归调用都会至少排除一个字母因此递归调用栈共有O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)层每一层的哈希表需要O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)的空间因此空间复杂度是O ( ∣ Σ ∣ 2 ) O(|\Sigma|^2)O(∣Σ∣2)。
RELATED

相关推荐

快速跑通GitHub开源项目:从环境配置到数据库迁移的完整指南

快速跑通GitHub开源项目:从环境配置到数据库迁移的完整指南

如果你想快速评估一个 GitHub 开源项目,最怕的往往不是文档太少,而是文档太多:README 从项目愿景写到 roadmap,几十个徽章,却没有清楚告诉你执行哪条命令能把它跑起来。kaneo 这类新开源项目很容易遇到这个问题——仓库…

📅 2026/11/11 13:21:06
开源看板Kaneo:自托管部署与团队落地指南

开源看板Kaneo:自托管部署与团队落地指南

当你的团队需要一套“数据完全在自己手里”的任务看板时,可选项并不像想象中那么多。Trello 简单好用,但数据在云端;Jira 功能强大,但对小团队来说配置和学习成本都很高;用 Excel 表格虽然零成本,却缺少任务…

📅 2026/11/11 15:20:04
常用办公脚本工具

常用办公脚本工具

1 前言 本文基于 Android 自动化测试项目、adb常用命令总结,整理了一些常用办公脚本,后续会根据工作需求持续更新。 脚本资源见→常用办公脚本工具 脚本目录如下: base:基础工具包apply:具体应用场景 注意:…

📅 2026/11/12 6:38:19
MORE NEWS

更多资讯

📰

北京煤气作业证通过率揭秘:实操考试心里没底怕挂科?洛阳建筑工人必看

北京煤气作业证通过率揭秘:实操考试心里没底怕挂科?洛阳建筑工人必看 实操考试心里没底怕挂科?这是很多准备报考北京煤气作业证的学员最真实的感受。尤其对于洛阳在职建筑工人来说,面对复杂的考试流程和高要求的实操考核,焦虑是常态。而真正能帮你上岸的…

📰

内江低压电工证复审在哪考?新手必看的办理流程与避坑指南

内江低压电工证复审在哪考?新手必看的办理流程与避坑指南 你是不是正在为找不到合适的工作发愁?是不是手里拿着一堆证书却还是找不到合适的机会?在当下, 急需特种作业证才能上岗找工作…

📰

米东区特种作业操作证全流程办理指南良心建议

米东区特种作业操作证全流程办理指南良心建议 你还在为找不到工作发愁?别急, 急需特种作业证才能上岗找工作 是摆在很多求职者面前的第一道门槛。特别是在新疆米东区,特种作业操作证不仅是上岗的“通行证”,更是你能否在市政、建筑、电力等行业立足的关…

📰

潮州电工证复审的地方在哪里 良心建议帮你少走弯路

潮州电工证复审的地方在哪里 良心建议帮你少走弯路 实操考试心里没底怕挂科?这事儿真不是你一个人的困扰。潮州电工证复审的地方在哪?怎么准备?怎么避免走弯路?这篇文章就是为了解决这些你心里没底的问题,给出 良心建议…

📰

电工证怎么考验英语 2026河南最新政策怎么影响你

电工证怎么考验英语 2026河南最新政策怎么影响你 怕考不过白交培训费,特别是2026河南最新政策下,电工证的考试流程和英语能力要求成了很多人关注的焦点。别急,本文从洛阳涧西区学员的实际案例出发,告诉你怎么避免“交了钱却白忙一场”的情况,让…

📰

小榄电工证在哪里报名网上查询全攻略学历不高也能考

小榄电工证在哪里报名网上查询全攻略学历不高也能考 你是不是也担心自己学历不高,连个电工证都报不了名?别慌,我跟你说,像我这样的在职建筑工人,学历不高照样能考小榄电工证,关键是你得知道 小榄电工证在哪里报名 ,还要会用 网上查询…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬