Longest Repeating Character Replacement

Q: What is the best time complexity for Longest Repeating Character Replacement?

Optimal (sliding window, max frequency never shrinks) runs in O(n) time and O(1) extra space. One pass with O(1) work per step; the left edge moves at most once per step.

Q: Which pattern does Longest Repeating Character Replacement use?

It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Substring Without Repeating Characters.

Q: Is there a brute force solution for Longest Repeating Character Replacement?

Yes. Brute force takes O(n²) time and O(1) space. Try every start index.

Q: Which edge cases should I test for Longest Repeating Character Replacement?

k = 0: the answer is the longest run of one letter; k at least the length: the whole string works; A single character; Every letter different, like "ABCDE" with k = 2: the answer is k + 1.

Medium Arrays & Hashing Sliding Window · Variable Original on LeetCode

Reported atUber Adobe

Longest Repeating Character Replacement is a medium arrays & hashing problem solved with the sliding window · variable pattern. The best approach, optimal (sliding window, max frequency never shrinks), runs in O(n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given a string s of uppercase English letters and an integer k. You may pick any position and change its letter to any other uppercase letter, at most k times in total.

Return the length of the longest substring that can be made to contain one repeated letter after those changes.

Examples

Example 1

Input: s = "BBCBAB", k = 1
Output: 4
Why: Change the C in "BBCB" to B to get four B's in a row. Every window of length 5 needs two changes.

Example 2

Input: s = "XYZXXY", k = 2
Output: 5
Why: Take "XYZXX" and change Y and Z to X to get five X's. The whole string would need three changes.

Example 3

Input: s = "QQQ", k = 0
Output: 3
Why: No changes are needed; the whole string is already one letter.

Constraints

1 <= s.length <= 10^5
s consists of uppercase English letters only.
0 <= k <= s.length

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force	`O(n²)`	`O(1)`
Better (sliding window, recount the top letter)	`O(26 · n)`	`O(1)`
Optimal (sliding window, max frequency never shrinks)	`O(n)`	`O(1)`

1Brute force

TimeO(n²)Every pair (i, j) is visited once with O(1) work.

SpaceO(1)A fixed array of 26 counts.

Try every start index. Extend the end one letter at a time while tracking letter counts and the highest count. The window [i, j] is fixable when its length minus the highest count is at most k; keep the longest such window.

For each start i, reset a count array of 26 and maxFreq = 0.
For each end j >= i: increase count[s[j]] and update maxFreq.
If (j - i + 1) - maxFreq <= k, update best with j - i + 1.

class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int best = 0;
        for (int i = 0; i < n; i++) {
            int[] count = new int[26];
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                int c = s.charAt(j) - 'A';
                count[c]++;
                maxFreq = Math.max(maxFreq, count[c]);
                if ((j - i + 1) - maxFreq <= k) {
                    best = Math.max(best, j - i + 1);
                }
            }
        }
        return best;
    }
}

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        best = 0
        for i in range(n):
            count = [0] * 26
            max_freq = 0
            for j in range(i, n):
                c = ord(s[j]) - ord('A')
                count[c] += 1
                max_freq = max(max_freq, count[c])
                if (j - i + 1) - max_freq <= k:
                    best = max(best, j - i + 1)
        return best

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        int best = 0;
        for (int i = 0; i < n; i++) {
            int count[26] = {0};
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                int c = s[j] - 'A';
                count[c]++;
                maxFreq = max(maxFreq, count[c]);
                if ((j - i + 1) - maxFreq <= k) {
                    best = max(best, j - i + 1);
                }
            }
        }
        return best;
    }
};

function characterReplacement(s, k) {
    const n = s.length;
    let best = 0;
    for (let i = 0; i < n; i++) {
        const count = new Array(26).fill(0);
        let maxFreq = 0;
        for (let j = i; j < n; j++) {
            const c = s.charCodeAt(j) - 65;
            count[c]++;
            maxFreq = Math.max(maxFreq, count[c]);
            if ((j - i + 1) - maxFreq <= k) {
                best = Math.max(best, j - i + 1);
            }
        }
    }
    return best;
}

2Better (sliding window, recount the top letter)

TimeO(26 · n)Each pointer moves at most n times, and each validity check scans 26 counts.

SpaceO(1)A fixed array of 26 counts.

Grow the window on the right. Whenever it needs more than k changes, drop letters from the left until it is valid again. To know how many changes a window needs, scan the 26 counts for the largest one.

Keep count[26] for the window [l, r].
For each r: add s[r].
While (r - l + 1) - max(count) > k: remove s[l] and increase l.
Update best with r - l + 1.

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            count[s.charAt(r) - 'A']++;
            while ((r - l + 1) - maxOf(count) > k) {
                count[s.charAt(l) - 'A']--;
                l++;
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }

    private int maxOf(int[] count) {
        int m = 0;
        for (int x : count) m = Math.max(m, x);
        return m;
    }
}

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = [0] * 26
        l = best = 0
        for r in range(len(s)):
            count[ord(s[r]) - ord('A')] += 1
            while (r - l + 1) - max(count) > k:
                count[ord(s[l]) - ord('A')] -= 1
                l += 1
            best = max(best, r - l + 1)
        return best

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> count(26, 0);
        int l = 0, best = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            count[s[r] - 'A']++;
            while ((r - l + 1) - *max_element(count.begin(), count.end()) > k) {
                count[s[l] - 'A']--;
                l++;
            }
            best = max(best, r - l + 1);
        }
        return best;
    }
};

function characterReplacement(s, k) {
    const count = new Array(26).fill(0);
    let l = 0, best = 0;
    for (let r = 0; r < s.length; r++) {
        count[s.charCodeAt(r) - 65]++;
        while ((r - l + 1) - Math.max(...count) > k) {
            count[s.charCodeAt(l) - 65]--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

3Optimal (sliding window, max frequency never shrinks)

TimeO(n)One pass with O(1) work per step; the left edge moves at most once per step.

SpaceO(1)A fixed array of 26 counts.

The answer only improves when a window has a higher top-letter count than any window before it. So keep maxFreq as the highest count ever seen and never lower it. If the window needs more than k changes, slide it by one (move l once) instead of shrinking it. The window size then never drops, and it only grows when a better maxFreq shows up. The final window size is the answer.

Keep count[26], l = 0, maxFreq = 0.
For each r: add s[r] and set maxFreq = max(maxFreq, count[s[r]]).
If (r - l + 1) - maxFreq > k: remove s[l] and increase l once.
Update best with r - l + 1.

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int l = 0, maxFreq = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            int c = s.charAt(r) - 'A';
            count[c]++;
            maxFreq = Math.max(maxFreq, count[c]);
            if ((r - l + 1) - maxFreq > k) {
                count[s.charAt(l) - 'A']--;
                l++;
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = [0] * 26
        l = max_freq = best = 0
        for r in range(len(s)):
            c = ord(s[r]) - ord('A')
            count[c] += 1
            max_freq = max(max_freq, count[c])
            if (r - l + 1) - max_freq > k:
                count[ord(s[l]) - ord('A')] -= 1
                l += 1
            best = max(best, r - l + 1)
        return best

class Solution {
public:
    int characterReplacement(string s, int k) {
        int count[26] = {0};
        int l = 0, maxFreq = 0, best = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            int c = s[r] - 'A';
            count[c]++;
            maxFreq = max(maxFreq, count[c]);
            if ((r - l + 1) - maxFreq > k) {
                count[s[l] - 'A']--;
                l++;
            }
            best = max(best, r - l + 1);
        }
        return best;
    }
};

function characterReplacement(s, k) {
    const count = new Array(26).fill(0);
    let l = 0, maxFreq = 0, best = 0;
    for (let r = 0; r < s.length; r++) {
        const c = s.charCodeAt(r) - 65;
        count[c]++;
        maxFreq = Math.max(maxFreq, count[c]);
        if ((r - l + 1) - maxFreq > k) {
            count[s.charCodeAt(l) - 65]--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Edge cases to test

k = 0: the answer is the longest run of one letter
k at least the length: the whole string works
A single character
Every letter different, like "ABCDE" with k = 2: the answer is k + 1

Hints

Hint 1

A window can be made into one letter if (window length) - (count of its most common letter) <= k.

Hint 2

As the right edge moves, when does the window become invalid, and how far must the left edge move to fix it?

Hint 3

You only care about windows longer than the best so far, so the stored maximum frequency never needs to go down.

FAQ

What is the best time complexity for Longest Repeating Character Replacement?

Optimal (sliding window, max frequency never shrinks) runs in O(n) time and O(1) extra space. One pass with O(1) work per step; the left edge moves at most once per step.

Which pattern does Longest Repeating Character Replacement use?

It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Substring Without Repeating Characters.

Is there a brute force solution for Longest Repeating Character Replacement?

Yes. Brute force takes O(n²) time and O(1) space. Try every start index.

Which edge cases should I test for Longest Repeating Character Replacement?

k = 0: the answer is the longest run of one letter; k at least the length: the whole string works; A single character; Every letter different, like "ABCDE" with k = 2: the answer is k + 1.