Problem Overview

  • You’re given a string s (uppercase letters only) and an integer k.
  • You can replace any character in the string up to k times.
  • Return the length of the longest substring containing the same letter after performing those replacements.

Brute Force

Intuition

The idea is straightforward — generate every possible substring, track the frequency of each character inside it, and check if the window is “valid.”

  • Try all possible substrings with two nested loops
  • Track character frequency within the current substring
  • Track maxFreq — the count of the most frequent character
  • If len - maxFreq <= k, the window is valid — update the result

How this works, we have the maxFreq of that substring if we subract it from the len then we got len of other chars. The string is only valid if the no of conversion we have to make is less than k that is length - maxFreq;

Code

class Solution {
public:
    int characterReplacement(string s, int k) {

        int n = s.size();
        int result = 0;

        for (int i = 0; i < n; i++) {

            vector freq = vector(26, 0);
            int maxFreq = 0;

            for (int j = i; j < n; j++) {

                freq[s[j] - 'A']++;
                maxFreq = max(maxFreq, freq[s[j] - 'A']);

                int len = j - i + 1;

                if (len - maxFreq <= k) {
                    result = max(result, len);
                }
            }
        }

        return result;
    }
};

Complexity

  • Time — O(n²)
  • Space — O(26) - O(1)

Why This Fails

This approach correctly identifies the answer — but it’ll get TLE on large inputs. The logic is sound though, and working through the brute force first is exactly what gives you the intuition needed to build the optimal solution.

Sliding Window

Intuition

  • we use the brute force logic and try to optimize it with sliding window.
  • we maintain a window with two pointers — i (left) and j (right) — both starting at 0.
  • We expand the window to the right and only shrink it from the left when it becomes invalid.
  • Expand j to the right, updating frequency and maxFreq
  • If (j - i + 1) - maxFreq > k, the window is invalid — move i right and update frequency
  • Once valid again, update the result with the current window size
  • We never shrink the result window, only slide it — this is what makes it linear

Code

class Solution {
public:
    int characterReplacement(string s, int k) {

        int n = s.size();
        vector freq = vector(26, 0);
        int maxFreq = 0;
        int result = 0;
        int i = 0;

        for (int j = 0; j < n; j++) {
            freq[s[j] - 'A']++;

            maxFreq = max(maxFreq, freq[s[j] - 'A']);

            while ((j - i + 1) - maxFreq > k) {
                freq[s[i] - 'A']--;
                i++;
            }

            result = max(result, j - i + 1);
        }

        return result;
    }
};

Complexity

  • Time — O(n)
  • Space — O(26) - O(1)

Key insight: maxFreq never decreases — even when we shrink the window. This is intentional. Our interest only lies in windows larger than the best we’ve already seen.

Key Takeaway

Always start with the brute force. Working through it forces you to think about the validity condition (len - maxFreq <= k), which is the core insight that directly translates into the sliding window. The optimal solution isn’t magic — it’s just the brute force, optimized.