# Longest Substring with At Least K Repeating Characters **Difficulty:** MEDIUM [External](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters) Canonical: https://scaleengineer.com/dsa/problems/longest-substring-with-at-least-k-repeating-characters **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window) **Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer) **Data structures:** Hash Table, String **Companies:** [Yandex](https://scaleengineer.com/companies/yandex), [Baidu](https://scaleengineer.com/companies/baidu) --- ## Problem 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 <= 104` * `s` consists of only lowercase English letters. * `1 <= k <= 105` # Approaches ## Brute Force with Substring Check This approach involves generating every possible substring of the input string `s` and, for each substring, checking if it satisfies the given condition. The condition is that every character present in the substring must appear at least `k` times. We keep track of the length of the longest valid substring found. **Time:** O(N^2). The two nested loops iterate through all `O(N^2)` substrings. For each substring, we check the validity by iterating through the 26-element frequency array, which takes constant time `O(1)`. Thus, the total time is `O(N^2 * 26)`, which simplifies to `O(N^2)`. · **Space:** O(1). We use a constant amount of extra space for the frequency array of size 26. **Pros:** Simple to understand and implement. **Cons:** Inefficient for large inputs and will likely result in a "Time Limit Exceeded" error on most platforms. ### Explanation We use two nested loops to define the start and end indices of all possible substrings. The outer loop iterates from `i = 0` to `n-1` (where `n` is the length of `s`), and the inner loop iterates from `j = i` to `n-1`. For each substring, we perform a check. To check a substring, we first count the frequency of each character within it. An array of size 26 can be used for this. As we extend the substring from `i` to `j`, we can update the frequency count in O(1) time. After updating the counts for the substring `s[i...j]`, we iterate through the frequency array. If we find any character whose count is greater than 0 but less than `k`, the substring is invalid. If all characters in the substring have a frequency of at least `k`, the substring is valid. We then update our maximum length result with the length of this current substring (`j - i + 1`). After checking all `O(N^2)` substrings, the maximum length recorded is the answer. ```java class Solution { public int longestSubstring(String s, int k) { int n = s.length(); if (n == 0 || k > n) { return 0; } int maxLength = 0; for (int i = 0; i < n; i++) { int[] counts = new int[26]; for (int j = i; j < n; j++) { counts[s.charAt(j) - 'a']++; if (isValid(counts, k, j - i + 1)) { maxLength = Math.max(maxLength, j - i + 1); } } } return maxLength; } private boolean isValid(int[] counts, int k, int length) { if (length < k) return false; for (int count : counts) { if (count > 0 && count < k) { return false; } } return true; } } ``` ### Algorithm 1. Initialize `maxLength = 0`. 2. Iterate through the string with a start index `i` from `0` to `n-1`. 3. For each `i`, iterate with an end index `j` from `i` to `n-1`. 4. Create a frequency map for the characters in the substring from `i` to `j`. 5. Set a flag `isValid = true`. 6. Iterate through the frequency map. If any character has a count `c` such that `0 < c < k`, set `isValid = false` and break. 7. If `isValid` is still true, update `maxLength = max(maxLength, j - i + 1)`. 8. After all loops complete, return `maxLength`. ## Divide and Conquer using Recursion This approach is based on a key observation: if a character `c` appears in the string `s` fewer than `k` times, it cannot be part of any valid substring. This is because any substring containing `c` would also have a frequency of `c` less than `k`. Therefore, such characters act as natural splitters. We can split the string by these "invalid" characters and recursively search for the longest valid substring in the resulting parts. **Time:** O(N^2) in the worst case. The worst-case scenario occurs when we only eliminate one character at each level of recursion (e.g., `s = "abacabada..."`, `k=2`), leading to a recursion depth of `O(N)`. At each level, we scan the substring, taking up to `O(N)` time. However, the average time complexity is much better, often cited as `O(N log N)`. · **Space:** O(N) in the worst case for the recursion call stack. **Pros:** More efficient than brute force on average.; It's an elegant and intuitive solution to the problem. **Cons:** The worst-case time complexity is still quadratic, which might be too slow for some specific test cases.; The recursion depth can go up to O(N), potentially causing a stack overflow for very large N, though unlikely with the given constraints. ### Explanation We define a recursive helper function that takes the start and end indices of a substring to consider. First, we handle the base case: if the length of the current substring is less than `k`, no valid substring is possible, so we return 0. Next, we build a frequency map for all characters within the current substring `s[start...end]`. We then iterate through the substring from `start` to `end`. If we find a character `s[i]` whose frequency is less than `k`, we know this character cannot be in our final answer. This "invalid" character `s[i]` splits the current problem into two independent subproblems: the part to its left (`s[start...i-1]`) and the part to its right (`s[i+1...end]`). We recursively call our function on both parts and return the maximum length found. If we scan the entire substring and find that every character has a frequency of at least `k`, it means the current substring `s[start...end]` is itself a valid candidate. We return its length, `end - start + 1`. ```java class Solution { public int longestSubstring(String s, int k) { return solve(s.toCharArray(), 0, s.length() - 1, k); } private int solve(char[] s, int start, int end, int k) { if (end - start + 1 < k) { return 0; } int[] counts = new int[26]; for (int i = start; i <= end; i++) { counts[s[i] - 'a']++; } for (int i = start; i <= end; i++) { if (counts[s[i] - 'a'] < k) { // This character is a splitter int left = solve(s, start, i - 1, k); int right = solve(s, i + 1, end, k); return Math.max(left, right); } } // If we reach here, the whole substring s[start...end] is valid return end - start + 1; } } ``` ### Algorithm 1. Define a recursive function `solve(s, start, end, k)`. 2. Base Case: If `end - start + 1 < k`, return 0. 3. Create a frequency map for the characters in the substring `s[start...end]`. 4. Iterate from `i = start` to `end`. 5. If the frequency of `s.charAt(i)` in the map is less than `k`: a. The character at `i` is a splitting point. b. The longest valid substring must be entirely to the left or right of `i`. c. Return `max(solve(s, start, i - 1, k), solve(s, i + 1, end, k))`. 6. If the loop completes without finding any splitting character, it means every character in `s[start...end]` appears at least `k` times. 7. The current substring is valid. Return its length `end - start + 1`. 8. The initial call is `solve(s, 0, s.length() - 1, k)`. ## Sliding Window with Fixed Number of Unique Characters A standard sliding window doesn't work directly because the validity condition is not monotonic (a valid substring can become invalid, then valid again by expanding the window). However, we can adapt the sliding window approach by adding an outer loop. The key insight is that any valid substring can have at most 26 unique characters. We can iterate through all possible numbers of unique characters (from 1 to 26), and for each possibility `h`, we find the longest substring that has exactly `h` unique characters, with each appearing at least `k` times. **Time:** O(N). The outer loop runs a constant number of times (26). The inner `while` loop with the `start` and `end` pointers processes each character of the string at most twice (once by `end` and once by `start`). Therefore, the complexity for each `h` is `O(N)`. The total time complexity is `O(26 * N)`, which is `O(N)`. · **Space:** O(1). We only use a constant amount of extra space for the frequency array of size 26. **Pros:** This is the most efficient approach with linear time complexity.; It's guaranteed to pass within the time limits for the given constraints. **Cons:** The logic is more complex to reason about and implement compared to the other approaches.; It requires understanding the specific constraints of the problem to come up with the idea of iterating on the number of unique characters. ### Explanation The main function will loop from `h = 1` to `h = 26`. Inside this loop, we solve a slightly different problem: "Find the longest substring with exactly `h` unique characters, where each character repeats at least `k` times." For a fixed `h`, we use a sliding window (`start`, `end`). We also maintain a frequency map `counts`, a count of unique characters in the window (`uniqueCount`), and a count of characters that meet the `k` frequency requirement (`countAtLeastK`). We expand the window by moving the `end` pointer. As we add a new character `s[end]`: - We update its frequency in `counts`. - If its count becomes 1, we increment `uniqueCount`. - If its count becomes `k`, we increment `countAtLeastK`. We shrink the window from the left (by moving `start`) whenever the number of unique characters `uniqueCount` exceeds our target `h`. As we remove `s[start]`: - If its count was `k`, we decrement `countAtLeastK`. - We decrement its frequency, and if it becomes 0, we decrement `uniqueCount`. After each expansion and potential shrinking, we check if our window is a candidate. A window is a candidate if `uniqueCount == h` and `countAtLeastK == h`. If so, we update our maximum length with the current window size (`end - start + 1`). The final answer is the maximum length found across all iterations for `h` from 1 to 26. ```java class Solution { public int longestSubstring(String s, int k) { int n = s.length(); int globalMax = 0; for (int h = 1; h <= 26; h++) { int[] counts = new int[26]; int start = 0, end = 0; int uniqueCount = 0; int countAtLeastK = 0; while (end < n) { // Expand window char charEnd = s.charAt(end); if (counts[charEnd - 'a'] == 0) { uniqueCount++; } counts[charEnd - 'a']++; if (counts[charEnd - 'a'] == k) { countAtLeastK++; } // Shrink window while (uniqueCount > h) { char charStart = s.charAt(start); if (counts[charStart - 'a'] == k) { countAtLeastK--; } counts[charStart - 'a']--; if (counts[charStart - 'a'] == 0) { uniqueCount--; } start++; } // Check for valid substring if (uniqueCount == h && countAtLeastK == h) { globalMax = Math.max(globalMax, end - start + 1); } end++; } } return globalMax; } } ``` ### Algorithm 1. Initialize `globalMax = 0`. 2. Loop `h` from 1 to 26 (for the number of unique characters). 3. Inside the loop, initialize a sliding window: `start = 0`, `counts = new int[26]`, `uniqueCount = 0`, `countAtLeastK = 0`. 4. Iterate `end` from 0 to `n-1`: a. Add `s.charAt(end)` to the window. Update `counts`, `uniqueCount`, and `countAtLeastK`. b. While `uniqueCount > h`: i. Remove `s.charAt(start)` from the window. Update `counts`, `uniqueCount`, and `countAtLeastK`. ii. Increment `start`. c. If `uniqueCount == h` and `countAtLeastK == h`: i. We have a valid substring for the current `h`. ii. Update `globalMax = max(globalMax, end - start + 1)`. 5. After the outer loop finishes, return `globalMax`. # Solutions ### Java ```java 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 ; } } ``` ### CPP ```cpp 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 ); } }; ``` ### Python ```python ''' >>> 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 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 ) ```