Longest Substring with At Least K Repeating Characters solution and explanation
Google
9 more videos on this problem
Longest Substring with At Least K Repeating Characters | LeetCode 395 | C++, Java, PythonKnowledge Center · 21:05 · 53K views
Longest Substring with At Least K Repeating Characters | Live Coding with Explanation | Leetcode#395Algorithms Made Easy · 5:31 · 31K views
Longest Substring with At Least K Repeating Characters | Leetcode 395 | Nov2020 Day 26 ChallenegCoding Decoded · 8:42 · 24K views
LeetCode 395. Longest Substring with At Least K Repeating CharactersHappy Coding · 24:14 · 11K views
Longest Substring with At Least K Repeating Characters | Leetcode 395Deep Coding · 7:08 · 6K views
Longest Substring with At Least K Repeating Characters - LeetCode Problem 395Forgotten Legends · 13:37 · 3K views
LeetCode 395. Longest Substring with At Least K Repeating Characters - Nov 26th - LeetCoding ChallenGoMaster Coding Interviews · 10:34 · 1K views
LeetCode 395 Longest Substring with At Least K Repeating CharactersAlgorithmicIQ · 25:40 · 1K views
Leetcode [395] Longest Substring with At Least K Repeating CharactersSDE Skills · 20:21 · 1K views
LeetCode 395 | Longest Substring with At Least K Repeating Characters | DFS | Recursion | JavaSleepy Cracker · 13:43 · 192 views
The problem
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.
def longestSubstring(s: str, k: int) -> int:
if len(s) == 0 or k > len(s):
return 0
if k <= 1:
return len(s)
char_count = {}
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1
for char in char_count:
if char_count[char] < k:
return max(longestSubstring(subs, k) for subs in s.split(char))
return len(s)function longestSubstring(s, k) {
if (s.length === 0 || k > s.length) return 0;
if (k <= 1) return s.length;
const charCount = {};
for (let char of s) {
charCount[char] = (charCount[char] || 0) + 1;
}
for (let char in charCount) {
if (charCount[char] < k) {
return Math.max(...s.split(char).map(sub => longestSubstring(sub, k)));
}
}
return s.length;
}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.
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.
import java.util.HashMap;
public class Solution {
public int longestSubstring(String s, int k) {
int maxLen = 0;
for (int numUnique = 1; numUnique <= 26; numUnique++) {
HashMap<Character, Integer> countMap = new HashMap<>();
int start = 0, end = 0, uniqueCount = 0, countAtLeastK = 0;
while (end < s.length()) {
if (uniqueCount <= numUnique) {
char c = s.charAt(end);
countMap.put(c, countMap.getOrDefault(c, 0) + 1);
if (countMap.get(c) == 1) uniqueCount++;
if (countMap.get(c) == k) countAtLeastK++;
end++;
} else {
char c = s.charAt(start);
if (countMap.get(c) == k) countAtLeastK--;
countMap.put(c, countMap.get(c) - 1);
if (countMap.get(c) == 0) uniqueCount--;
start++;
}
if (uniqueCount == numUnique && uniqueCount == countAtLeastK) {
maxLen = Math.max(maxLen, end - start);
}
}
}
return maxLen;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
#include <string>
using namespace std;
int longestSubstring(string s, int k) {
int maxLen = 0;
for (int numUnique = 1; numUnique <= 26; ++numUnique) {
unordered_map<char, int> countMap;
int start = 0, end = 0, uniqueCount = 0, countAtLeastK = 0;
while (end < s.size()) {
if (uniqueCount <= numUnique) {
char c = s[end];
if (countMap[c]++ == 0) uniqueCount++;
if (countMap[c] == k) countAtLeastK++;
end++;
} else {
char c = s[start];
if (countMap[c]-- == k) countAtLeastK--;
if (countMap[c] == 0) uniqueCount--;
start++;
}
if (uniqueCount == numUnique && uniqueCount == countAtLeastK) {
maxLen = max(maxLen, end - start);
}
}
}
return maxLen;
}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.
Time Complexity: O(n), leveraging sliding window efficiency.
Space Complexity: O(1), because frequency data is constant in space complexity.
Approach 3: Default Approach
func longestSubstring(s string, k int) int {
var dfs func(l, r int) int
dfs = func(l, r int) int {
cnt := [26]int{}
for i := l; i <= r; i++ {
cnt[s[i]-'a']++
}
var split byte
for i, v := range cnt {
if v > 0 && v < k {
split = byte(i + 'a')
break
}
}
if split == 0 {
return r - l + 1
}
i := l
ans := 0
for i <= r {
for i <= r && s[i] == split {
i++
}
if i > r {
break
}
j := i
for j <= r && s[j] != split {
j++
}
t := dfs(i, j-1)
ans = max(ans, t)
i = j
}
return ans
}
return dfs(0, len(s)-1)
}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), leveraging sliding window efficiency. |
| Default Approach | – |
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. |
Frequently asked questions
Is Longest Substring with At Least K Repeating Characters easy or hard?
The problem is rated Medium because the constraint that every character must appear at least k times makes brute-force substring checks impractical. Recognizing that invalid characters split the string or that the sliding window must be constrained by unique counts requires deeper algorithmic insight.
Longest Substring with At Least K Repeating Characters Python/Java solution
Python implementations commonly use the divide and conquer approach with recursion and a Counter or dictionary for frequency counting. Java solutions often implement the sliding window strategy using an integer array of size 26 for character frequencies. Both approaches achieve optimal or near-optimal time complexity depending on the method used.
How to solve Longest Substring with At Least K Repeating Characters in O(n)?
Use a sliding window and iterate over the number of allowed unique characters. Maintain character frequency counts, a unique character counter, and a counter for characters meeting the k frequency requirement. Expand the window with the right pointer and shrink with the left pointer when constraints break. When both counters match, update the maximum substring length.
What is the best approach for Longest Substring with At Least K Repeating Characters?
The most efficient approach uses a sliding window combined with iterating over the possible number of unique characters. For each unique character target (1–26), expand and shrink a window while tracking frequencies. This ensures every character in the window appears at least k times. The time complexity becomes O(26 * n), which is effectively O(n) for lowercase English letters.
Is Longest Substring with At Least K Repeating Characters asked at Google/Amazon/Meta?
This problem appears frequently in interviews at large tech companies because it tests string manipulation, frequency counting, and advanced sliding window logic. Variants of the problem have been reported in interviews at Amazon, Google, and Meta, especially for mid-level software engineering roles.
What data structure is used in Longest Substring with At Least K Repeating Characters?
The main data structure is a frequency counter implemented with an array or hash table. It tracks how many times each character appears in the current substring or segment. Combined with two pointers for sliding window or recursive splitting for divide and conquer, it enables efficient validation of the k-repetition condition.
What is the time complexity of Longest Substring with At Least K Repeating Characters?
The sliding window solution runs in O(26 * n) time because the algorithm scans the string once for each possible count of unique characters. Since the alphabet size is constant, this simplifies to O(n). The divide and conquer method typically runs in O(n log n) time due to recursive splits and repeated frequency counting.