Medium — Sliding Window | Two Pointers | Hash Map | String

The Problem

Find the length of the longest substring containing the same letter that you can get after performing at most k character replacements. You can replace any character in the string with any other uppercase English letter.

Approach

Use a sliding window approach with two pointers to maintain a valid window where the number of characters to replace (window size minus most frequent character count) doesn’t exceed k. Expand the window by moving the right pointer and shrink it by moving the left pointer when the replacement count exceeds k.

Time: O(n) · Space: O(1)

Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left, right = 0, 0
        max_length = 0
        char_freq = {}
        max_freq = 0

        while right < len(s):
            char_freq[s[right]] = char_freq.get(s[right], 0) + 1
            max_freq = max(max_freq, char_freq[s[right]])

            if (right - left + 1) - max_freq > k:
                char_freq[s[left]] -= 1
                left += 1

            max_length = max(max_length, right - left + 1)
            right += 1

        return max_length

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment