【2.27】LeetCode每日一题· 至少有K个重复字符的最长子串

2021年02月27日 10时56分

标签： LeetCode dfs

## 题目描述
给你一个字符串`s`和一个整数`k` ，请你找出`s`中的最长子串，要求该子串中的每一字符出现次数都不少于`k`。返回这一子串的长度。

#### 示例1
	输入：s = "aaabb", k = 3
	输出：3
	解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

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

#### 提示
	1 <= s.length <= 10^4
	s 仅由小写英文字母组成
	1 <= k <= 10^5
	
#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/submissions/ "题目链接")

## 解题思路
在思考的过程中，本想二分答案求解，但是这是错误的思路。因为满足题意的最长字串长度并不满足**单调性**的特征，即不满足**假设ans是满足子串中出现的每一字符次数都不少于k次的子串长度，那么$$\forall a < ans$$也满足这一条件**（这一点很好判断）。

需要换一种思路。由于题目要求`该子串中的每一字符出现次数都不少于k`，因此如果**某一字符在整个串中的出现次数小于`k`，那么它不可能包含在答案子串中**。因此，我们可以统计所有出现次数小于`k`的字符，把这些字符看作分隔符将原串分割成若干子串，再递归地对这些子串进行判断。如果递归到某一子串时，其中不存在出现次数小于`k`的字符，那么该子串就是可行解之一。最后取最大的可行子串的长度作为答案即可。

##代码
	#!C++
	class Solution {
	public:
		int dfs(string& s, int l, int r, int k){
			vector<int> cnt(26, 0);
			for(int i = l; i < r; i++){
				cnt[s[i]-'a']++;
			}
			char split = 0;
			for(int i = 0; i < 26; i++){
				if(cnt[i] > 0 && cnt[i] < k){
					split = i+'a';
					break;
				}
			}
			if(split == 0){
				return r-l;
			}
			int i = l, j = l, res = 0, temp = 0;
			while(j < r){
				if(s[j] == split){
					temp = dfs(s, i, j, k);
					res = max(res, temp);
					i = j+1; 
				}
				j++;
			}
			temp = dfs(s, i, j, k);
			res = max(res, temp);
			return res;
		}

int longestSubstring(string s, int k) {
			return dfs(s, 0, s.length(), k);
		}
	};

## 用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：8.7 MB，在所有 C++提交中击败了14.56%的用户

所有评论

166****5019 2021年02月27日 22:23:16
还可以使用滑动窗口解答

参与主题/评论回复

166****5019 发表于2021年02月27日 22:23:16
还可以使用滑动窗口解答

回复评论

邮箱

图形验证码

邮箱验证码
- 166****5019 2021年02月27日 22:24:30
  是的，说的很正确
  
  参与主题/评论回复
  
  166****5019 发表于2021年02月27日 22:24:30
  是的，说的很正确
  
  回复评论
  
  邮箱
  
  图形验证码
  
  邮箱验证码

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2.27】LeetCode每日一题· 至少有K个重复字符的最长子串

所有评论

新增评论