# 395. Longest Substring with At Least K Repeating Characters (Medium)

https://leetcode.com/problems/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.
```

## Solutions

``````class Solution {

// Traverse the string with a specified window size in which we calculate all the char frequency.

// Every time you walk forward one step, decrease the frequency of the char excluded from the window
// and increase the frequency of the char included into the window.

public int longestSubstring(String s, int k) {
int ans = 0;

if (s == null || s.length() < k) {
return ans;
}

int len = s.length();

if (k <= 1) {
return len;
}

for (int ws = k; ws <= len; ws++) {

int[] freq = new int;
Arrays.fill(freq, 0);

// initialize the char frequency in the first window
for (int i = 0; i < ws; i++) {
char c = s.charAt(i);
freq[c - 'a']++;
}

// last is the last char in the window
for (int last = ws - 1; last < len; last++) {
int c = s.charAt(last);

// do not add, we should check out the frequency of the first window
if (last != ws - 1) {
char exc = s.charAt(last - ws);
char inc = s.charAt(last);

freq[exc - 'a']--;
freq[inc - 'a']++;
}

// if the newly included char meets the requirement, check the whole frequency
// of current window.
if (freq[c - 'a'] > 0 && freq[c - 'a'] >= k && check(freq, k)) {
// overwrite previous max length
ans = ws;
}
}
}

return ans;
}

private boolean check(int[] freq, int k) {

for (int i = 0; i < freq.length; i++) {

// exists but the frequency doesn't meet the requirement.

if (freq[i] > 0 && freq[i] < k) {
return false;
}
}

return true;
}
}
``````