Longest Repeating Character Replacement

LeetCode 424 | Difficulty: Medium

Medium

Problem Description

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Constraints:

- `1 <= s.length <= 10^5`

- `s` consists of only uppercase English letters.

- `0 <= k <= s.length`

Topics: Hash Table, String, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 99 ms)

Metric	Value
Runtime	99 ms
Memory	36.1 MB
Date	2022-02-09

Solution

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int[] counts = new int[128];
    int others = 0, n = s.Length, maxFreq = 0, result=0;
    int i = 0;
    for (int j = 0; j < s.Length; j++)
    {
        counts[s[j]-'A']++;
        maxFreq = Math.Max(maxFreq, counts[s[j]-'A']);
        others = (j-i+1)-maxFreq;
        if(others>k)
        {
            counts[s[i]-'A']--;
            i++;
        }
        result = Math.Max(result, j-i+1);
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.