Longest Substring with At Least K Repeating Characters

Medium

📘 Problem Statement

Given a string s and an integer k, return the length of the longest substring of s such that every character in the substring appears at least k times.

---

🔍 Example

s = "aaabb"
k = 3
print(longestSubstring(s, k))  # Output: 3, because "aaa" is valid

---

Intuition

We want the longest substring where each character appears at least k times. A brute force solution checking all substrings would be \(O(n^2)\) and inefficient.

Instead, we’ll use Divide and Conquer (recursive approach). The idea:

• If a character occurs less than k times, it cannot be part of the valid substring.
• So we use that character as a split point and recursively solve for the substrings around it.

🛠️ Solution

🧑‍💻 Code

def longestSubstring(s: str, k: int) -> int:
    if len(s) < k:
        return 0

    # Count frequency of each character
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1

    for ch in freq:
        if freq[ch] < k:
            # Split by invalid character
            return max(longestSubstring(t, k) for t in s.split(ch))

    # All characters in this substring appear at least k times
    return len(s)

🕒 Time Complexity: Worst case: \(O(n^2)\) due to repeated splits. Usually much faster in practice due to pruning invalid characters early.