Longest Substring with At Least K Repeating Characters

Med

#0382Time: 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.2 companies

Patterns

Algorithms

Data structures

Companies

Prompt

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 <= 10⁴
s consists of only lowercase English letters.
1 <= k <= 10⁵

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

Initialize maxLength = 0.
Iterate through the string with a start index i from 0 to n-1.
For each i, iterate with an end index j from i to n-1.
Create a frequency map for the characters in the substring from i to j.
Set a flag isValid = true.
Iterate through the frequency map. If any character has a count c such that 0 < c < k, set isValid = false and break.
If isValid is still true, update maxLength = max(maxLength, j - i + 1).
After all loops complete, return maxLength.

Walkthrough

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.

1class Solution {2    public int longestSubstring(String s, int k) {3        int n = s.length();4        if (n == 0 || k > n) {5            return 0;6        }7        int maxLength = 0;8        for (int i = 0; i < n; i++) {9            int[] counts = new int[26];10            for (int j = i; j < n; j++) {11                counts[s.charAt(j) - 'a']++;12                if (isValid(counts, k, j - i + 1)) {13                    maxLength = Math.max(maxLength, j - i + 1);14                }15            }16        }17        return maxLength;18    }19 20    private boolean isValid(int[] counts, int k, int length) {21        if (length < k) return false;22        for (int count : counts) {23            if (count > 0 && count < k) {24                return false;25            }26        }27        return true;28    }29}

Complexity

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.

Trade-offs

Pros

Simple to understand and implement.

Cons

Inefficient for large inputs and will likely result in a "Time Limit Exceeded" error on most platforms.

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.

Algorithm

Define a recursive function solve(s, start, end, k).
Base Case: If end - start + 1 < k, return 0.
Create a frequency map for the characters in the substring s[start...end].
Iterate from i = start to end.
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)).
If the loop completes without finding any splitting character, it means every character in s[start...end] appears at least k times.
The current substring is valid. Return its length end - start + 1.
The initial call is solve(s, 0, s.length() - 1, k).

Walkthrough

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.

1class Solution {2    public int longestSubstring(String s, int k) {3        return solve(s.toCharArray(), 0, s.length() - 1, k);4    }5 6    private int solve(char[] s, int start, int end, int k) {7        if (end - start + 1 < k) {8            return 0;9        }10        11        int[] counts = new int[26];12        for (int i = start; i <= end; i++) {13            counts[s[i] - 'a']++;14        }15        16        for (int i = start; i <= end; i++) {17            if (counts[s[i] - 'a'] < k) {18                // This character is a splitter19                int left = solve(s, start, i - 1, k);20                int right = solve(s, i + 1, end, k);21                return Math.max(left, right);22            }23        }24        25        // If we reach here, the whole substring s[start...end] is valid26        return end - start + 1;27    }28}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Initialize globalMax = 0.
Loop h from 1 to 26 (for the number of unique characters).
Inside the loop, initialize a sliding window: start = 0, counts = new int[26], uniqueCount = 0, countAtLeastK = 0.
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).
After the outer loop finishes, return globalMax.

Walkthrough

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.

1class Solution {2    public int longestSubstring(String s, int k) {3        int n = s.length();4        int globalMax = 0;5 6        for (int h = 1; h <= 26; h++) {7            int[] counts = new int[26];8            int start = 0, end = 0;9            int uniqueCount = 0;10            int countAtLeastK = 0;11 12            while (end < n) {13                // Expand window14                char charEnd = s.charAt(end);15                if (counts[charEnd - 'a'] == 0) {16                    uniqueCount++;17                }18                counts[charEnd - 'a']++;19                if (counts[charEnd - 'a'] == k) {20                    countAtLeastK++;21                }22                23                // Shrink window24                while (uniqueCount > h) {25                    char charStart = s.charAt(start);26                    if (counts[charStart - 'a'] == k) {27                        countAtLeastK--;28                    }29                    counts[charStart - 'a']--;30                    if (counts[charStart - 'a'] == 0) {31                        uniqueCount--;32                    }33                    start++;34                }35                36                // Check for valid substring37                if (uniqueCount == h && countAtLeastK == h) {38                    globalMax = Math.max(globalMax, end - start + 1);39                }40                41                end++;42            }43        }44        return globalMax;45    }46}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ); } };

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 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ; } }

1class 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 ); } };

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 )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.