首页 > 代码库 > LeetCode-Longest Substring with At Least K Repeating Characters
LeetCode-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.
Analysis:
Given a string s, find out all chars that are invalid (i.e., count < k). The longest substring must reside in one of the substrings divided by those invalid chars. We find out all those possible substrings and recursively address each of them.
NOTE: repeatedly using s.charAt() is actually very slow. If we use charAt() in the following code, the runtime becomes 6ms, doubled!
Solution:
public class Solution { public int longestSubstring(String s, int k) { return longestSubstringRecur(s,k); } public int longestSubstringRecur(String s, int k){ if (s.length()<k) return 0; int[] charCounts = new int[26]; for (int i=0;i<s.length();i++){ char c = s.charAt(i); charCounts[c-‘a‘]++; } // Early termination: // 1. invalid: no char in s appears >= k times. // Or 2. Good enough: every char appears >= k times. boolean valid = false, goodEnough = true; for (int count : charCounts){ if (count>=k){ valid = true; } if (count>0 && count <k){ goodEnough = false; } if (valid && !goodEnough) break; } if (!valid) return 0; if (goodEnough) return s.length(); // Address every valid substring, i.e., substring between two invalid chars. int p1=0, p2=-1, maxLen=0; while (p1<s.length()){ p2++; while (p2<s.length() && charCounts[s.charAt(p2)-‘a‘]>=k) p2++; int curMaxLen = longestSubstringRecur(s.substring(p1,p2),k); maxLen = Math.max(maxLen,curMaxLen); p1 = p2+1; } return maxLen; }}
bstring T of a given string (consists of lowercase letters only) such that every character in T appears
LeetCode-Longest Substring with At Least K Repeating Characters