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[26];
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;
}
}