424. Longest Repeating Character Replacement - Leetcode Solution

Leetcode Problem Link Code Solution Link:

💡 Step-by-Step Thought Process

Understand the problem: Find the length of the longest substring that can be made to have all the same character by replacing at most k characters.
Initialize longest to 0 to track the longest valid substring and left pointer l to 0.
Create an array counts of size 26 to track the frequency of each uppercase letter.
Iterate through each right index r from 0 to the length of s.
Increment the count of s[r] in counts using its ASCII value (i.e. ord(s[r]) - 65).
While the window size (i.e. r - l + 1) minus the maximum frequency in counts exceeds k, decrement the count of s[l] and increment l to shrink the window.
Update longest to the maximum of longest and the current window size (i.e. r - l + 1).
Return longest after the loop.

Code Solution

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        longest = 0
        l = 0
        counts = [0] * 26

        for r in range(len(s)):
            counts[ord(s[r]) - 65] += 1

            while (r - l + 1) - max(counts) > k:
                counts[ord(s[l]) - 65] -= 1
                l += 1

            longest = max(longest, (r - l + 1))

        return longest

# Time Complexity: O(n)
# Space Complexity: O(1)

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> counts(26, 0);
        int l = 0, longest = 0, maxCount = 0;

        for (int r = 0; r < s.size(); r++) {
            maxCount = max(maxCount, ++counts[s[r] - 'A']);

            while ((r - l + 1) - maxCount > k) {
                counts[s[l] - 'A']--;
                l++;
            }

            longest = max(longest, r - l + 1);
        }

        return longest;
    }
};

public class Solution {
    public int characterReplacement(String s, int k) {
        int[] counts = new int[26];
        int l = 0, longest = 0;
        int maxCount = 0;

        for (int r = 0; r < s.length(); r++) {
            maxCount = Math.max(maxCount, ++counts[s.charAt(r) - 'A']);

            while ((r - l + 1) - maxCount > k) {
                counts[s.charAt(l) - 'A']--;
                l++;
            }

            longest = Math.max(longest, r - l + 1);
        }

        return longest;
    }
}

var characterReplacement = function(s, k) {
    const counts = new Array(26).fill(0);
    let l = 0, longest = 0, maxCount = 0;

    for (let r = 0; r < s.length; r++) {
        maxCount = Math.max(maxCount, ++counts[s.charCodeAt(r) - 65]);

        while ((r - l + 1) - maxCount > k) {
            counts[s.charCodeAt(l) - 65]--;
            l++;
        }

        longest = Math.max(longest, r - l + 1);
    }

    return longest;
};

Detailed Explanation

Understanding the Problem: Longest Repeating Character Replacement

The goal of this problem is to find the longest substring where we can make all characters the same by replacing no more than k characters. The most effective approach for this type of problem is the sliding window technique.

The core idea is to maintain a "window" (a substring from a left to a right pointer) and a frequency count of the characters within that window. We expand this window by moving the right pointer and check if the current window is "valid".

A window is considered valid if the number of characters we would need to replace to make it a single-character string is less than or equal to k. This can be expressed with a simple formula: window_length - count_of_most_frequent_character <= k. If the window becomes invalid, we shrink it by moving the left pointer to the right, ensuring the condition is met again. We keep track of the maximum valid window size we have seen so far.

For example, given the string "AABABBA" and k = 1, the longest substring with repeating characters produced by replacing at most k characters would be "[AABA]BBA" or "AA[BABB]A". Hence, the output should be 4.

Why This Problem Is Important

This is a foundational problem in the category of sliding window techniques. It's widely used in software interviews to assess a candidate's ability to manipulate pointers and use auxiliary data structures to solve real-time string-processing tasks efficiently.

Time and Space Complexity

The sliding window technique ensures that each character is added to and removed from the sliding window at most once. This results in a time complexity of O(n), where n is the length of the string. The space complexity is O(1), since the length of counts is always 26, which does not change as the length of the input string s changes.

Conclusion

The “Longest Repeating Character Replacement” problem is an elegant demonstration of how sliding window techniques can be used to reduce time complexity from exponential to linear. By keeping track of the characters dynamically and efficiently adjusting the window, we achieve both clarity and performance. This makes the solution highly scalable and applicable to real-time input processing such as streaming text or log data.

Get Personalized Support at AlgoMap Bootcamp 💡

AlgoMap.io

Want Help Cracking FAANG?