Domain 2MediumCORE

Longest Substring with At Least K Repeating Characters

We are given a string s and an integer k. Our goal is to find the maximum length of any substring where every character within that specific substring appears at least k times within that same substring.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Divide and Conquer#Recursion#Sliding Window

395. Longest Substring with At Least K Repeating Characters

Model: qwen3.5:9b
Topics: Divide and Conquer,Recursion,Sliding Window
FAANG asked: 1
Acceptance rate: 43.6%


Problem Breakdown

We are given a string s and an integer k. Our goal is to find the maximum length of any substring where every character within that specific substring appears at least k times within that same substring.

Inputs:

  • A lowercase English string s.
  • An integer k.

Outputs:

  • Integer representing the max valid length. If no such substring exists, return 0.

Constraints & Edge Cases to consider:

  1. Empty or short strings: If len(s) < k, it’s impossible for any character to appear k times, so result is 0.
  2. No solution possible: Even if the whole string has valid counts globally, a specific substring might not satisfy the condition (e.g., “ab”, k=1 -> both ‘a’ and ‘b’ count >= 1? Wait, example says freq of each char in this substring must be >=k. If s=“abc”, k=2. No char appears twice. Result 0).
  3. All characters valid: The whole string is the answer.
  4. Splitting logic: A character that fails to meet frequency k acts as a “wall”. Any valid substring cannot cross this specific occurrence of that character because including it would violate its own count constraint relative to k (or rather, if we include an instance where total count < k in the current window, that window is invalid).

Intuition

Let’s start with brute force. We could iterate through every possible substring O(N2)O(N^2) and for each one calculate character frequencies O(N)O(N). That gives us O(N3)O(N^3) or optimized to O(N2)O(N^2) using a sliding window count update, but the condition “every char ≥k\ge k” is tricky with standard sliding windows because shrinking from the left might fix counts on the right side in complex ways.

The key insight here comes from Divide and Conquer. If we look at any character c that appears fewer than k times within a specific segment of string, then any valid substring cannot contain all occurrences of c. In fact, since every char inside the target substring must have count ≥k\ge k, if there is an instance of a character whose total frequency in our current window is <k< k, that entire occurrence breaks validity.

Wait, strictly speaking: If we are looking at a segment and find a character (say ‘a’) with frequency 2 where k=3, then no valid substring can include any part of the string that spans across these occurrences in a way that keeps them together? Actually, simpler logic: If a specific character has count <k< k in our current window, we cannot form a valid substring crossing this instance. Therefore, any valid solution must lie entirely to the left or entirely to the right of every occurrence of characters with frequency <k< k.

So, if we find all characters that appear fewer than k times in the current string segment:

  1. We split the string at each index where these “invalid” characters occur.
  2. This creates smaller sub-problems (left and right segments).
  3. We recursively solve for those segments.

Since there are only 26 lowercase letters, counting frequencies is fast (O(N)O(N)), and splitting reduces problem size effectively.

Approach

  1. Define a recursive helper function solve(s).
  2. Base Case: If the length of string passed to recursion is less than k, return 0 immediately (impossible to satisfy condition).
  3. Count Frequencies: Use a hash map or Counter to get frequencies of all characters in current segment ss.
  4. Identify Invalid Characters: Iterate through unique keys in the counter. If any character has count < k:
    • This character acts as a separator. We must split s at every occurrence of this invalid character.
  5. Split and Recurse:
    • Collect all indices where these “bad” characters appear (or simply iterate through string to find them).
    • Split the original segment into sub-segments excluding those bad occurrences.
    • Call solve() on each valid sub-segment.
  6. Combine Results: The result for current call is the maximum of results from all recursive calls. If no characters had count <k< k, return length of string (entire substring is valid).

Complexity Analysis

  • Time Complexity: O(N)O(N), where N is s.length.
    • Although it looks like recursion might be exponential, each character belongs to exactly one node in the recursion tree at a specific depth. Because we split on invalid characters and discard them from consideration (they are never counted again), plus alphabet size Σ\Sigma is constant (26). The work done per level of recursion across all sub-problems sums up linearly with respect to N. Specifically, counting takes O(N)O(N) but the sum of lengths processed at each depth doesn’t exceed a small multiple of NN.
  • Space Complexity: O(1)O(1) auxiliary space (excluding input) or technically O(Σ)O(\Sigma) for frequency map where Σ=26\Sigma=26, plus recursion stack. In worst case, if string is like “abc…z” repeated such that we split every time, depth could be proportional to N in pathological cases without memoization? Actually with alphabet constraint 26, the number of distinct characters causing splits is limited per level logic effectively keeping it efficient enough for N=104N=10^4. Python recursion limit might hit on very specific worst-case inputs (e.g. all unique chars), but given constraints and typical test cases, this fits standard limits.

Solution

from collections import Counter

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # Helper function for recursion/Divide & Conquer logic
        def solve(sub_s):
            n = len(sub_s)
            
            # Base case: if string length is less than k, no valid substring possible
            if n < k:
                return 0
            
            # Count frequencies of characters in current segment
            counts = Counter(sub_s)
            
            # If all characters appear at least k times, the whole segment is valid
            # We check this by seeing if any char has count < k. 
            # Note: Using a loop over unique chars (max 26).
            split_indices = []
            for char in counts:
                if counts[char] < k:
                    # Find all indices of invalid characters to split around them
                    idx_list = [i for i, c in enumerate(sub_s) if c == char]
                    split_indices.extend(idx_list + 1) 
                    
            # If no character has count < k, return length of current segment
            if not any(counts[char] < k for char in counts):
                return n
            
            # Split the string at invalid characters and recurse on valid parts
            max_len = 0
            prev_idx = -1
            
            for idx in split_indices:
                left_part = sub_s[prev_idx + 1 : idx]
                right_part = sub_s[idx + 1 :] 
                
                # Recursively solve for segments between invalid chars
                if len(left_part) > max_len:
                    max_len = max(max_len, solve(left_part))
            
            # Handle the last segment after the last split index (if any)
            # Actually simpler logic is to iterate through indices and slice. 
            # Let's refine splitting loop for clarity in implementation below
            
            return max(solve(sub_s[prev_idx + 1 : idx]) if prev_idx != -1 else solve(""), ...) 
            
        # Wait, the slicing logic above inside recursion needs careful handling of boundaries
        # Re-writing cleaner split logic:
        
        def helper(segment):
            n = len(segment)
            if n < k or not segment: return 0
            
            counts = Counter(segment)
            
            # Check for any character with count < k
            invalid_chars = {char for char, cnt in counts.items() if cnt < k}
            
            if not invalid_chars:
                return n
                
            max_len = 0
            start_idx = 0
            
            for i, char in enumerate(segment):
                if char in invalid_chars:
                    # Found a separator. Solve left part and reset window
                    right_part = segment[i + 1:] 
                    
                    # Recurse on the valid chunk before this split
                    max_len = max(max_len, helper(segment[start_idx:i]))
                    
                    start_idx = i + 1
            
            # Don't forget to solve for the remaining suffix after last invalid char found
            if len(segment) > n: # Logic check needed? 
                pass
                
            return max(len(segment), max_len)

        # Let's implement standard clean recursion logic directly in main function
        
    def longestSubstring(self, s: str, k: int) -> int:
        def solve(sub_s):
            if len(sub_s) < k or not sub_s:
                return 0
            
            counts = Counter(sub_s)
            
            # Identify characters that break validity (freq < k)
            invalid_chars = [char for char, count in counts.items() if count < k]
            
            if not invalid_chars:
                return len(sub_s)
                
            max_len = 0
            
            # Split string at every occurrence of these invalid chars
            prev_idx = -1
            for i, c in enumerate(sub_s):
                if c in invalid_chars:
                    left_part = sub_s[prev_idx + 1 : i]
                    right_part = sub_s[i + 1:] 
                    
                    # Recurse on valid parts. Note: we don't need to pass empty strings explicitly here, slicing handles it
                    
            return max_len

        return solve(s)

Wait, the code logic above in thought block is getting messy with indices. I will write a cleaner implementation for the final output that correctly slices and recurses on valid segments between invalid characters.

Correct Logic:

  1. Count chars.
  2. If all ≥k\ge k, return len.
  3. Else find split points (indices of bad chars).
  4. Recurse on sub_s[0:i] for each bad char at i, and finally recurse on remaining suffix after last bad char.

Edge Cases Handled

  • Empty string: Returns 0 immediately via length check or slicing logic returning empty segments which return 0.
  • k > len(s): Base case returns 0.
  • No valid substring exists (e.g., “abc”, k=2): All chars have count < k, splits result in empty strings -> max_len remains 0.
  • All characters meet criteria: invalid_chars list is empty, function returns full length immediately.
from collections import Counter

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # Helper recursive function for Divide and Conquer approach
        def solve(sub_s):
            n = len(sub_s)
            
            # Base case: if string is empty or shorter than k, no valid substring possible
            if not sub_s or n < k:
                return 0
            
            counts = Counter(sub_s)
            
            # Identify characters that appear fewer than k times in current segment.
            # These act as "walls" because any valid substring cannot contain them 
            # (since their frequency would be less than k).
            invalid_chars = {char for char, count in counts.items() if count < k}
            
            # If no such characters exist, the entire string is a valid candidate.
            if not invalid_chars:
                return n
            
            max_len = 0
            start_idx = 0
            
            # Iterate through the segment to find split points (occurrences of bad chars)
            for i in range(n):
                char_at_i = sub_s[i]
                
                if char_at_i in invalid_chars:
                    # Found a separator. Recurse on the valid substring before this index.
                    left_part = sub_s[start_idx : i]
                    max_len = max(max_len, solve(left_part))
                    
                    # Update start for next segment after this bad character
                    start_idx = i + 1
            
            # After loop finishes, check if there is a valid suffix remaining 
            # (from the last invalid char to end of string)
            right_part = sub_s[start_idx : n]
            max_len = max(max_len, solve(right_part))
            
            return max_len

        return solve(s)