The O(n) Club: Become the Overlord of Longest Repeating Character Replacements (Sliding Window Style)

The O(n) Club: Become the Overlord of Longest Repeating Character Replacements (Sliding Window Style)

⚡ TL;DR

Here’s the interview classic everyone loves to mangle: Find the length of the longest substring that could become all one letter, if you replaced up to k of its annoying non-matching rebels. But don’t actually mutate a single thing—just play the What If game, Java-style.

// Please don't do this (for the love of your CPU):
int max = 0;
for (int i = 0; i < s.length(); i++) {
  for (int j = i; j < s.length(); j++) {
    int[] freq = new int[26];
    int maxFreq = 0;
    for (int m = i; m <= j; m++) {
      maxFreq = Math.max(maxFreq, ++freq[s.charAt(m) - 'A']);
    }
    if ((j - i + 1) - maxFreq <= k) max = Math.max(max, j - i + 1);
  }
}
// This is how you fry a laptop battery!

🧠 How Devs Usually Mess This Up

Ah, fresh interview nerves! Most folks try to actually swap letters, as if racing for the World Record in String Mutation. Some try to count all frequencies in every possible window—turning a perfectly nice O(n) problem into a musical chair apocalypse of nested loops. And many get tripped up by the shrinking: just remember, when your window needs more than k changes to unify, slide the left end over and try again. Easy does it. Breathe.

🔍 What’s Actually Going On

Imagine your string is a line of very opinionated robots. They all want to match, but some are just being difficult. You own a sliding window: for any position, you tally the most popular robot type (the Max Frequency King) inside that window. The rest? They’re ripe for up to k firmware swaps. If you can unite everyone in the window by swapping at most k rebels, you expand. If not, you eject the leftmost one and keep moving. It’s like hosting a party where you can only afford to fix k guests’ personalities before the fun stops.

🛠️ PseudoCode

• Initialize: left = 0, maxCount = 0, maxLength = 0, counts[26] for robot (er, character) types.
• Expand window rightward: For each right from 0 to N:
  • Bump up counts[s.charAt(right)-'A']
• Track the kingpin: Update maxCount to be the highest freq in window so far.
• If your rebels exceed budget: When (right - left + 1) - maxCount > k, kick out s.charAt(left) and left++.
• Keep score: Update maxLength with window as you go.

• int[] counts = new int[26];
  int left = 0, maxCount = 0, maxLength = 0;
  for (int right = 0; right < s.length(); right++) {
    counts[s.charAt(right) - 'A']++;
    maxCount = Math.max(maxCount, counts[s.charAt(right) - 'A']);
    if ((right - left + 1) - maxCount > k) {
      counts[s.charAt(left) - 'A']--;
      left++;
    }
    maxLength = Math.max(maxLength, right - left + 1);
  }