Longest Substring with At Least K Repeating Characters

medium string divide and conquer sliding window

Problem

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

Inputs = "ababbc", k = 2

Output5

"ababb" has a×2 and b×3; 'c' is the lonely character that splits the answer off.

def longest_substring(s, k):
    if len(s) < k: return 0
    from collections import Counter
    cnt = Counter(s)
    for c in cnt:
        if cnt[c] < k:
            return max(longest_substring(part, k) for part in s.split(c))
    return len(s)

function longestSubstring(s, k) {
  if (s.length < k) return 0;
  const cnt = {};
  for (const c of s) cnt[c] = (cnt[c] || 0) + 1;
  for (const c of Object.keys(cnt)) {
    if (cnt[c] < k) {
      return Math.max(...s.split(c).map(p => longestSubstring(p, k)));
    }
  }
  return s.length;
}

class Solution {
    public int longestSubstring(String s, int k) {
        if (s.length() < k) return 0;
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (cnt[s.charAt(i) - 'a'] < k) {
                int best = 0;
                for (String part : s.split(String.valueOf(s.charAt(i))))
                    best = Math.max(best, longestSubstring(part, k));
                return best;
            }
        }
        return s.length();
    }
}

int longestSubstring(string s, int k) {
    if ((int)s.size() < k) return 0;
    int cnt[26] = {0};
    for (char c : s) cnt[c - 'a']++;
    for (int i = 0; i < (int)s.size(); i++) {
        if (cnt[s[i] - 'a'] < k) {
            int best = 0, j = 0;
            for (int t = 0; t <= (int)s.size(); t++) {
                if (t == (int)s.size() || s[t] == s[i]) {
                    best = max(best, longestSubstring(s.substr(j, t - j), k));
                    j = t + 1;
                }
            }
            return best;
        }
    }
    return s.size();
}

Explanation

The key observation is about weak characters: if some letter appears fewer than k times in the whole string, it can never be part of any valid answer. So that letter acts like a wall that splits the string into smaller pieces.

This gives a clean divide and conquer approach. Count every character. If they all already appear at least k times, the entire string is valid and we just return its length.

Otherwise we pick a character c whose total count is below k, split the string on c, and recursively solve each piece. The answer is the best result across all the pieces.

Example: s = "ababbc", k = 2. Here c appears only once, so it splits the string into "ababb" and "". In "ababb" every letter (a×2, b×3) meets k, so its length 5 is the answer.

Each split removes at least one distinct character from consideration, so the recursion depth is bounded by the alphabet size, keeping it efficient.

Time: O(n · 26) in practice (recursion depth bounded by alphabet) Space: O(n)