The O(n) Club: Longest Substring with At Least K Repeating Characters — Chop Shop Edition

The O(n) Club: Longest Substring with At Least K Repeating Characters — Chop Shop Edition

⚡ TL;DR

Your PM says, “Give me the longest substring where every letter appears at least k times.” Sure, right after you finish boiling the ocean with a brute-force solution. Or, you know, you could be smart: for any ‘slacker’ character whose count is under k, split the string and recursively chop each piece. Welcome to substrings, but make it professional.

// If you enjoy O(n^2) and existential dread:
public int longestSubstring(String s, int k) {
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        int[] freq = new int[26];
        for (int j = i; j < s.length(); j++) {
            freq[s.charAt(j)-'a']++;
            if (allAtLeastK(freq, k)) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
}
// But don't. Scroll on.

🧠 How Devs Usually Mess This Up

Dev logic: “I’ll check every substring.” Upper bound, O(n^2). Lower bound for your sanity, however, approaches zero. And don’t be that person who tries to ‘remove’ unpopular letters from the entire string—you need substrings, not a Frankenstein ransom note. If you skip over a char, the substring gets broken, and the interviewer gets disappointed.

🔍 What’s Actually Going On

Picture your string as a block party, and each unique character is a guest. If a guest shows up less than k times, that’s your cue—they’re the ones killing the vibe. So you break the party at their seat, split the string, and keep recursing on each fun-sized chunk. The club only pops when every remaining guest is sufficiently rowdy (k or more appearances). Think VIP rope, but for code.

🛠️ PseudoCode

• Count frequency of each character in your substring.
  • int[] freq = new int[26]; Classic Java, no trendy Maps here.
• If all characters show up at least k times, congrats!
  • Return the length of the substring. Go grab a snack.
• If you find a character with < k appearances:
  • Split at that spot and recursively solve left/right—one chunk at a time.
• Base case: Substring shorter than k? Not even worth the interviewer’s side-eye—return 0.

💻 The Code

public int longestSubstring(String s, int k) {
    return helper(s, 0, s.length(), k);
}
 private int helper(String s, int start, int end, int k) {
    if (end - start < k) return 0;
    int[] freq = new int[26];
    for (int i = start; i < end; i++) freq[s.charAt(i) - 'a']++;
    for (int i = start; i < end; i++) {
        if (freq[s.charAt(i) - 'a'] < k) {
            int next = i + 1;
            while (next < end && freq[s.charAt(next) - 'a'] < k) next++;
            return Math.max(
                helper(s, start, i, k),
                helper(s, next, end, k)
            );
        }
    }
    return end - start;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Substring is too short? If it’s less than k, there’s literally no way every char repeats k times. Fast exit.
• Splitting all at once? Wrong. You have to split around each cluster of “bad” chars—no skipping chunks.
• Don’t trust your brute force timer. O(n^2) will run for hours. Divide-and-conquer is O(n) (thanks, fixed alphabet!).
• Memory drama? Nope. You only use a humble little array, size 26. The real leak is probably that Chrome tab from 2018.

🧠 Interviewer Brain-Tattoo

“When life gives you slacker chars, break the string—don’t break your spirit. That’s how real devs survive substring interviews.”