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 <= 104s consists of only lowercase English letters.1 <= k <= 105In #395 Longest Substring with At Least K Repeating Characters, the goal is to find the longest substring where every character appears at least k times. A powerful strategy uses Divide and Conquer. First, count the frequency of characters in the current substring using a hash table. Any character whose frequency is less than k cannot be part of a valid substring. These characters act as split points that divide the string into smaller segments. Recursively evaluate each segment and take the maximum valid length.
Another effective idea is a sliding window combined with limiting the number of distinct characters. Iterate over possible counts of unique characters and maintain a window that tracks frequencies. When every character inside the window appears at least k times, update the answer.
The divide‑and‑conquer approach is intuitive and prunes invalid regions quickly, while the sliding window approach systematically explores valid character distributions. Both rely on frequency counting for efficient validation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Divide and Conquer with Frequency Split | O(n log n) average, up to O(n^2) worst case | O(1) to O(26) for character frequency |
| Sliding Window by Unique Character Count | O(26 * n) | O(26) |
NeetCode
This approach uses recursion to divide the string into smaller parts based on characters that do not meet the frequency threshold k. The recursive function checks the entire string and divides it at points where a character occurs fewer than k times. The algorithm then recursively checks each of these substrings, calculating the longest valid substring length for each, and returns the maximum of these lengths.
Time Complexity: O(n log n), where n is the length of the string, due to string splitting and recursion.
Space Complexity: O(n), for the recursion stack and character frequency hashmap.
1function longestSubstring(s, k) {
2 if (s.length === 0 || k > s.length) return 0;
3 if (k <= 1) return s.length;
4
5 const charCount = {};
6
7 for (let char of s) {
8 charCount[char] = (charCount[char] || 0) + 1;
9 }
10
11 for (let char in charCount) {
12 if (charCount[char] < k) {
13 return Math.max(...s.split(char).map(sub => longestSubstring(sub, k)));
14 }
15 }
16
17 return s.length;
18}Similar to the Python solution, this implementation uses an object to keep track of character frequencies. It splits the string at characters that don't meet the minimum frequency requirement and recursively processes each part to find the maximum valid substring length.
This approach works by using the sliding window technique. The idea is to maintain a window with a maximum unique count of characters and check if the conditions are met for each window. The algorithm adjusts the window boundaries to ensure all characters within the window occur at least k times.
Time Complexity: O(n), as each character is processed at most twice.
Space Complexity: O(1), as the space used by the character frequency array is constant.
1import java.util.HashMap;
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations have appeared in technical interviews at major tech companies. It tests understanding of string processing, frequency counting, divide and conquer strategies, and advanced sliding window techniques.
Yes, a sliding window approach can be applied by iterating over the possible number of unique characters. The window expands and shrinks while tracking character counts, ensuring each character appears at least k times before updating the result.
A common optimal approach uses divide and conquer. Characters that appear fewer than k times cannot belong to a valid substring, so they are used as split points to recursively evaluate smaller segments. This efficiently narrows the search space.
A hash table or fixed-size frequency array is typically used to count character occurrences within substrings. Since the input consists of lowercase letters, an array of size 26 is often the most efficient choice.
In this Java solution, similar to the C++ version, a sliding window is implemented with two pointers iterating through possible unique characters. A hashmap provides the tracking mechanism for character frequencies within the window. The variable numUnique defines the distinct character limits being considered for each iteration.