Scale Engineer

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
Sliding Window
Algorithms
Divide and Conquer
Data structures
Hash TableString
Companies
YandexBaidu

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 <= 104
  • s consists of only lowercase English letters.
  • 1 <= k <= 105

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

  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.

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.

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

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.

Solutions

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

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 →

Next problem