# 395. Longest Substring with At Least K Repeating Characters

## Description

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

if no such substring exists, return 0.

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.


Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.


Constraints:

• 1 <= s.length <= 104
• s consists of only lowercase English letters.
• 1 <= k <= 105

## Solutions

Use a divide and conquer approach. This problem asks for the length of the longest substring where each character appears at least k times. The key insight is that if a character x appears in the substring less than k times, then any valid substring cannot include x and must lie entirely on one side of x. Thus, x acts as a divider for potential valid substrings.

### How It Works:

1. Base Case: If the string’s length is less than k, it’s impossible for any character to appear k times, so return 0.

2. Character Frequency: Use Counter from the collections module to count the frequency of each character in s.

3. Divide and Conquer:
• Iterate through the character frequencies. If any character char appears less than k times, it cannot be part of the longest valid substring. Thus, char acts as a divider.
• Split the string s at char and apply the function recursively to each segment. This step divides the problem into smaller subproblems.
• The max function is used on the result of the recursive calls to ensure that the longest valid substring length is returned.
4. Valid Substring: If the loop completes without finding any character that appears less than k times, the entire string s is a valid substring. Thus, return the length of s.

This divide and conquer solution efficiently reduces the problem size by splitting the string into smaller segments whenever an invalid character is found, leading to a direct path toward finding the longest substring where each character appears at least k times.

• class Solution {
private String s;
private int k;

public int longestSubstring(String s, int k) {
this.s = s;
this.k = k;
return dfs(0, s.length() - 1);
}

private int dfs(int l, int r) {
int[] cnt = new int[26];
for (int i = l; i <= r; ++i) {
++cnt[s.charAt(i) - 'a'];
}
char split = 0;
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0 && cnt[i] < k) {
split = (char) (i + 'a');
break;
}
}
if (split == 0) {
return r - l + 1;
}
int i = l;
int ans = 0;
while (i <= r) {
while (i <= r && s.charAt(i) == split) {
++i;
}
if (i > r) {
break;
}
int j = i;
while (j <= r && s.charAt(j) != split) {
++j;
}
int t = dfs(i, j - 1);
ans = Math.max(ans, t);
i = j;
}
return ans;
}
}

• class Solution {
public:
int longestSubstring(string s, int k) {
function<int(int, int)> dfs = [&](int l, int r) -> int {
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 = 'a' + i;
break;
}
}
if (split == 0) {
return r - l + 1;
}
int i = l;
int ans = 0;
while (i <= r) {
while (i <= r && s[i] == split) {
++i;
}
if (i >= r) {
break;
}
int j = i;
while (j <= r && s[j] != split) {
++j;
}
int t = dfs(i, j - 1);
ans = max(ans, t);
i = j;
}
return ans;
};
return dfs(0, s.size() - 1);
}
};

• '''
>>> s = "ababbc"
>>> set(s)
{'b', 'a', 'c'}

>>> s.count('a')
2
>>> s.count('b')
3

>>> s.split('a')
['', 'b', 'bbc']
'''

class Solution:
def longestSubstring(self, s: str, k: int) -> int:
for c in set(s):
# no need to try all chars with count<k, get the 1st one and return
if s.count(c) < k: # @note: This character must not appear in any substring
return max([self.longestSubstring(t, k) for t in s.split(c)])
return len(s)

class Solution: # iterative, OJ passed
def longestSubstring(self, s: str, k: int) -> int:
n = len(s)
result = 0

# Iterate over the possible values of unique characters in the substring
for num_unique in range(1, 27):
freq_map = [0] * 26
left = 0
num_chars = 0
num_chars_at_least_k = 0

# Sliding window approach to find the longest substring with num_unique characters
for right in range(n):
if freq_map[ord(s[right]) - ord('a')] == 0:
num_chars += 1
freq_map[ord(s[right]) - ord('a')] += 1
if freq_map[ord(s[right]) - ord('a')] == k:
num_chars_at_least_k += 1

# Shrink the window if the number of unique characters exceeds num_unique
while num_chars > num_unique:
freq_map[ord(s[left]) - ord('a')] -= 1
if freq_map[ord(s[left]) - ord('a')] == k - 1:
num_chars_at_least_k -= 1
if freq_map[ord(s[left]) - ord('a')] == 0:
num_chars -= 1
left += 1

# Check if all characters in the substring occur at least k times
if num_chars == num_chars_at_least_k:
result = max(result, right - left + 1)

return result

############

class Solution:
def longestSubstring(self, s: str, k: int) -> int:
def dfs(l, r):
cnt = Counter(s[l : r + 1])
split = next((c for c, v in cnt.items() if v < k), '')
if not split:
return r - l + 1
i = l
ans = 0
while i <= r:
while i <= r and s[i] == split:
i += 1
if i >= r:
break
j = i
while j <= r and s[j] != split:
j += 1
t = dfs(i, j - 1)
ans = max(ans, t)
i = j
return ans

return dfs(0, len(s) - 1)


• func longestSubstring(s string, k int) int {
var dfs func(l, r int) int
dfs = func(l, r int) int {
cnt := [26]int{}
for i := l; i <= r; i++ {
cnt[s[i]-'a']++
}
var split byte
for i, v := range cnt {
if v > 0 && v < k {
split = byte(i + 'a')
break
}
}
if split == 0 {
return r - l + 1
}
i := l
ans := 0
for i <= r {
for i <= r && s[i] == split {
i++
}
if i > r {
break
}
j := i
for j <= r && s[j] != split {
j++
}
t := dfs(i, j-1)
ans = max(ans, t)
i = j
}
return ans
}
return dfs(0, len(s)-1)
}