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; for(int i = 0; i <= s.length() - k; i++){ for(int j = i + k; j <= s.length(); j++){ String t = s.substring(i, j); if(help(t, k)){ res = Math.max(res, j - i); } } } return res; } public boolean help(String s, int k){ int[] arr = new int[128]; for(char c: s.toCharArray()) arr[c]++; for(int i: arr){ if(i != 0 && i < k) return false; } return true; } }
1. brute force, TLE
class Solution { public int longestSubstring(String s, int k) { if (s == null || s.length() == 0) return 0; if (k<2) return s.length(); return helper(s, 0, s.length(), k); } public int helper(String s, int l, int r, int k) { if (l>=r) return 0; // build freq map int[] freq = new int[26]; for (int i=l; i<r; i++) freq[s.charAt(i)-‘a‘]++; // check if valid boolean valid = true; for (int i=0; i<26 && valid; i++) if (freq[i] > 0 && freq[i] < k) valid = false; if (valid) return r-l; // if not for each invalid character start a new split search int best = 0, start=l; for (int i=l; i<r; i++) { if (freq[s.charAt(i) -‘a‘] < k) { best = Math.max(best, helper(s, start, i, k)); start = i+1; } } best = Math.max(best, helper(s, start, r, k)); return best; } }
395. Longest Substring with At Least K Repeating Characters
原文：https://www.cnblogs.com/wentiliangkaihua/p/13167410.html