# 395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

``````Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.
``````

Example 2:

``````Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
``````

``````class Solution {
public:
int longestSubstring(string s, int k) {
int res = 0, i = 0, n = s.size();
while (i + k <= n) {
int m[26] = {0}, mask = 0, max_idx = i;
for (int j = i; j < n; ++j) {
int t = s[j] - 'a';
++m[t];
if (m[t] < k) mask |= (1 << t);
else mask &= (~(1 << t));
res = max(res, j - i + 1);
max_idx = j;
}
}
i = max_idx + 1;
}
return res;
}
};
``````

``````class Solution {
public:
int longestSubstring(string s, int k) {
int res = 0, n = s.size();
for (int cnt = 1; cnt <= 26; ++cnt) {
int start = 0, i = 0, uniqueCnt = 0;
vector<int> charCnt(26);
while (i < n) {
bool valid = true;
if (charCnt[s[i++] - 'a']++ == 0) ++uniqueCnt;
while (uniqueCnt > cnt) {
if (--charCnt[s[start++] - 'a'] == 0) --uniqueCnt;
}
for (int j = 0; j < 26; ++j) {
if (charCnt[j] > 0 && charCnt[j] < k) valid = false;
}
if (valid) res = max(res, i - start);
}
}
return res;
}
};
``````

``````class Solution {
public:
int longestSubstring(string s, int k) {
int n = s.size(), max_idx = 0, res = 0;
int m[128] = {0};
bool ok = true;
for (char c : s) ++m[c];
for (int i = 0; i < n; ++i) {
if (m[s[i]] < k) {
res = max(res, longestSubstring(s.substr(max_idx, i - max_idx), k));
ok = false;
max_idx = i + 1;
}
}
return ok ? n : max(res, longestSubstring(s.substr(max_idx, n - max_idx), k));
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/395

Longest Substring with At Most K Distinct Characters

Longest Substring with At Most Two Distinct Characters

Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87834/onlogn-recursive-cpp-solution

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87739/Java-Strict-O(N)-Two-Pointer-Solution

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87749/Two-short-C%2B%2B-solutions-(3ms-and-6ms)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation