Welcome to Subscribe On Youtube
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 <= 104sconsists 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:
-
Base Case: If the string’s length is less than
k, it’s impossible for any character to appearktimes, so return0. -
Character Frequency: Use
Counterfrom thecollectionsmodule to count the frequency of each character ins. - Divide and Conquer:
- Iterate through the character frequencies. If any character
charappears less thanktimes, it cannot be part of the longest valid substring. Thus,characts as a divider. - Split the string
satcharand apply the function recursively to each segment. This step divides the problem into smaller subproblems. - The
maxfunction is used on the result of the recursive calls to ensure that the longest valid substring length is returned.
- Iterate through the character frequencies. If any character
- Valid Substring: If the loop completes without finding any character that appears less than
ktimes, the entire stringsis a valid substring. Thus, return the length ofs.
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) }