Leetcode 395. 至少有K个重复字符的最长子串 C++

Leetcode 395. 至少有K个重复字符的最长子串

题目

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

测试样例

示例 1:

输入: s = "aaabb", k = 3 输出: 3 最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2:

输入: s = "ababbc", k = 2 输出: 5 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

题解

递归 由题意可知，我们不能让目标字符串中有一个字符其出现次数小于k。我们先用一个哈希表记录字符出现的次数。 我们现在令pre=0,然后开始遍历字符串，如果有一个字符s[i]其出现次数小于k了，显然我们的目标字符串不能含有这个字符，我们就判断pre~i-1是否存在我们的目标字符串，我们获取这个字符串，然后递归调用函数。 之后，我们需要判断i+1 ~ s.length中是否存在我们的目标字符串，我们现更新一下哈希表，因为pre~i肯定是不能用了，我们同时将pre=i+1。重复上述过程 详细过程见代码

代码

int longestSubstring(string s, int k) { unordered_map<char,int> list; int l = s.length(); for(int i=0; i<l; i++) list[s[i]]++; int pre = 0,ans=0,cnt=0,i; for(i=0; i<l; i++){ if(list[s[i]] < k){ ans = max(ans,longestSubstring(s.substr(pre,i-pre),k)); //判断pre~i-1中是否函数目标字符串 cnt++; while(pre != i+1){ //舍弃pre~i，更新哈希表 list[s[pre]]--; pre++; } } } ans = max(ans,i-pre); //最后一段字符串可能也是目标字符串 if(cnt == 0) return s.length(); else return ans; }

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。