Longest Substring with At Least K Repeating Characters - Solution & Explanation
Problem Statement
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 <= 104sconsists of only lowercase English letters.1 <= k <= 105
Approach Overview
Problem Overview: Given a string s and an integer k, find the length of the longest substring where every character appears at least k times. The substring must be contiguous, and any character that appears fewer than k times invalidates that segment.
Approach 1: Divide and Conquer (O(n log n) time, O(n) space)
This strategy recursively splits the string around characters that cannot be part of a valid substring. First, count the frequency of each character in the current segment using a hash map. Any character whose frequency is less than k cannot appear in a valid result. Use such characters as split points and recursively evaluate the left and right substrings. If every character in the segment already satisfies the constraint, the entire segment length is valid. The key insight: invalid characters partition the problem into smaller independent substrings. This method works well because each recursive call processes smaller segments and avoids checking impossible candidates repeatedly. It heavily relies on frequency counting with a hash table and recursion typical of divide and conquer problems.
Approach 2: Sliding Window with Variable Unique Character Constraint (O(26 * n) time, O(1) space)
This approach iterates over possible counts of unique characters and uses a sliding window to maintain substrings that satisfy the constraint. For each target number of distinct characters (1 through 26 for lowercase letters), expand the window with two pointers. Track character frequencies and maintain two counters: the number of unique characters and the number of characters that appear at least k times. When the unique count exceeds the target, shrink the window from the left. When both counts match, the window represents a valid substring where every character repeats at least k times. This converts the global constraint into a manageable window condition and systematically explores all valid configurations. The technique combines frequency tracking with the sliding window pattern.
Recommended for interviews: The sliding window approach demonstrates stronger algorithmic control and typically achieves near-linear performance. Interviewers often expect candidates to recognize that brute force substring checks are inefficient and then transition to either divide-and-conquer splitting or a constrained sliding window. Showing the recursive split first proves understanding of the constraint, while implementing the sliding window highlights optimization skills.
Approach 1: Divide and Conquer Approach
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.
This implementation uses a hashmap to count occurrences of each character in the input string. If any character's count is less than k, it splits the string into substrings around each such character. It recursively calls itself for each of these substrings, and finally, returns the maximum length found. Base conditions handle edge cases like empty strings and where k is less than or equal to one.
Code
Python
JavaScript
Complexity
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.
Approach 2: Sliding Window Approach with Variable Constraints
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.
The C++ solution employs two pointers to define the window's start and end. It iterates over possible unique character counts and uses a hashmap to track character frequency. It expands the window by moving the end pointer and contracts by moving the start if constraints are violated. The current valid window's length gets evaluated against the maximum length found so far.
Complexity
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.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Divide and Conquer Approach | Time Complexity: O(n log n), where n is the length of the string, due to string splitting and recursion. |
| Sliding Window Approach with Variable Constraints | Time Complexity: O(n), as each character is processed at most twice. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer | O(n log n) average | O(n) | Good when recursion and string partitioning are easier to reason about. Useful for explaining the invalid-character insight. |
| Sliding Window with Unique Count Iteration | O(26 * n) ≈ O(n) | O(1) | Preferred optimal solution for interviews and large inputs. Efficient because the alphabet size is constant. |
Video Solution
Longest Substring with At Least K Repeating Characters | LeetCode 395 | C++, Java, Python • Knowledge Center • 53,047 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Substring with At Least K Repeating Characters easy or hard?
Longest Substring with At Least K Repeating Characters Python/Java solution
How to solve Longest Substring with At Least K Repeating Characters in O(n)?
What is the best approach for Longest Substring with At Least K Repeating Characters?
Is Longest Substring with At Least K Repeating Characters asked at Google/Amazon/Meta?
What data structure is used in Longest Substring with At Least K Repeating Characters?
What is the time complexity of Longest Substring with At Least K Repeating Characters?
Ready to solve this problem?
Practice Longest Substring with At Least K Repeating Characters with our built-in code editor and test cases.
Practice on FleetCode