Here is the problem for Longest Repeating Character Replacement.

1. Understand the problem

• Let me restate the problem in my own words: I’m given a string of uppercase letters, and I can replace at most k characters to make a substring that has all the same letter. I need to return the length of the longest such substring.

2. Ask clarifying questions

• What is the maximum possible length of s? (constraint check)

• Can s be empty? If yes, should I return 0?

• Are letters guaranteed to be uppercase A–Z only?

• Is k always non-negative?

• What is the expected time complexity? O(n), O(n^2)?

3. Work through examples

1. Example 1:

s = "ABAB", k = 2 → Replace 2 Bs → "AAAA" → length 4

1. Edge cases:

s = "", k = 1 → Output = 0

s = "AAAA", k = 2 → Already all same → 4

4. Brainstorm 2–3 solutions

4.1. Naive approach (Brute Force)

• For each substring, count how many changes needed to make it uniform.

• If ≤ k, track max length.

• Time complexity: O(N^2).

4.2. Optimized approach (Sliding Window)

• Use a window that expands when valid.

• Maintain count of each char in window.

• The window is valid if:

window_length - max_freq <= k

• Slide window when invalid.

• Time complexity: O(n)

• Space complexity: O(26)

• Note: With the left, the max length is [left, right] that match window_length - max_freq <= k.

5. Implement solutions

5.1. Brute Force

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        res = 0
        for i in range(len(s)):
            count, maxf = {}, 0
            for j in range(i, len(s)):
                count[s[j]] = 1 + count.get(s[j], 0)

                # Track maxf real-time
                maxf = max(maxf, count[s[j]])

                # If the gap <= k, update res
                if (j - i + 1) - maxf <= k:
                    res = max(res, j - i + 1)
        return res

• Time complexity: O(N^2).

• Space complexity: O(M).

m: is the total number of unique characters in the string.

5.2. Sliding Window

• Idea: Go from left to right, if count small => move left to another count.

=> If count increase and gap larger than k, we shrink from left, otherwise continue count.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        res = 0
        charSet = set(s)

        for c in charSet:
            count = l = 0
            for r in range(len(s)):
                if s[r] == c:
                    count += 1

                while (r - l + 1) - count > k:
                    if s[l] == c:
                        count -= 1
                    l += 1

                res = max(res, r - l + 1)
        return res

• Time complexity: O(N * M).

• Space complexity: O(M).

m: is the total number of unique characters in the string = (N - max_freq).

5.3. Sliding Window (Optimal)

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        res = 0

        l = 0
        maxf = 0
        for r in range(len(s)):
            count[s[r]] = 1 + count.get(s[r], 0)
            maxf = max(maxf, count[s[r]])

            while (r - l + 1) - maxf > k:
                count[s[l]] -= 1
                l += 1
            res = max(res, r - l + 1)

        return res

• Time complexity: O(N).

• Space complexity: O(M).

Note:

• Because l is increasing, time complexity must be O(N) but not O(N^2).

• (r - l + 1) is the window_size and maxf is the max frequent number

Why time complexity is not O(N∗(curr_window_size−curr_max_freq−k))

• Due to left and right is increasing => curr_window_size−curr_max_freq−k must be a constant.

Note:

• In Sliding Window, due to left and right are increasing together, the total traverse is O(2N)

• And with the current left => We only have a subarray that have the value of length, so we can increase it.

6. Dry run example

1. Example 1: s = “abcde”, k = 1

Step	r	l (after shrink)	Window	len	maxf	len - maxf	Valid?	res
0	0	0	A	1	1	0	✅	1
1	1	0	AB	2	1	1	✅	2
2	2	1	BC	2	1	1	✅	2
3	3	2	CD	2	1	1	✅	2
4	4	3	DE	2	1	1	✅	2

1. Example: s = “AABABBA”, k = 1

Step	r	s[r]	count	maxf	(r-l+1)-maxf	Valid?	l after	res	Window
1	0	A	{A:1}	1	0	✅	0	1	A
2	1	A	{A:2}	2	0	✅	0	2	AA
3	2	B	{A:2,B:1}	2	1	✅	0	3	AAB
4	3	A	{A:3,B:1}	3	1	✅	0	4	AABA
5	4	B	{A:3,B:2}	3	2	❌	1	4	ABAB
6	5	B	{A:2,B:3}	3	1	✅	1	5	ABABB
7	6	A	{A:3,B:3}	3	1	✅	1	6	ABABBA