Longest Substring with At Least K Repeating Characters

MEDIUM

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

Approaches

Checkout 3 different approaches to solve Longest Substring with At Least K Repeating Characters. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: O(1). We use a constant amount of extra space for the frequency array of size 26.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

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

Code Solutions

Checking out 3 solutions in different languages for Longest Substring with At Least K Repeating Characters. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Longest Substring with At Least K Repeating Characters

Algorithms:

Divide and Conquer

Patterns:

Sliding Window

Data Structures:

Hash TableString

Companies:

Yandex |Baidu |