多语言企业网站模板,个人公司如何注册,360网站怎么建设,优质主页格式1. 题目
找到给定字符串#xff08;由小写字符组成#xff09;中的最长子串 T #xff0c; 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入:
s aaabb, k 3
输出:
3
最长子串为 aaa #xff0c;其中 a 重复了 3 次。示…1. 题目
找到给定字符串由小写字符组成中的最长子串 T 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入:
s aaabb, k 3
输出:
3
最长子串为 aaa 其中 a 重复了 3 次。示例 2:
输入:
s ababbc, k 2
输出:
5
最长子串为 ababb 其中 a 重复了 2 次 b 重复了 3 次。来源力扣LeetCode 链接https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
找出字符串中次数小于 k 的他们不能出现在答案中以他们的位置把字符串切开递归求解子问题当一个子串中字符计数都 k 时更新最大长度剪枝当前处理的字符串长度 最大长度时不再递归处理
class Solution {int maxlen 0;
public:int longestSubstring(string s, int k) {if(s.size() maxlen)//剪枝return 0;int count[26] {0}, i, left 0;for(i 0; i s.size(); i)count[s[i]-a];vectorint split;for(i 0; i s.size(); i){if(count[s[i]-a] 0 count[s[i]-a] k)split.push_back(i);//不能出现的字符位置}if(split.empty())maxlen max(maxlen, int(s.size()));//没有切分位置满足题意for(i 0; i split.size(); i){longestSubstring(s.substr(left, split[i]-left), k);left split[i]1;if(i split.size()-1 left s.size())longestSubstring(s.substr(left, s.size()-left), k);}return maxlen;}
};8 ms 6.8 MB
