Longest Repeating Character Replacement

medium
Sliding WindowStringSliding WindowHash Table

Given a string s and an integer k, you can choose any character of the string and change it to any other uppercase English letter. 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.

In other words, find the longest window in s where the number of characters that need to be replaced (characters that are not the most frequent character in the window) is at most k.

Examples

Example 1

  • Input: s = "ABAB", k = 2
  • Output: 4
  • Explanation: Replace the two 'A's with 'B's or vice versa. The entire string becomes a repeating character substring.

Example 2

  • Input: s = "AABABBA", k = 1
  • Output: 4
  • Explanation: Replace the one 'B' at index 3 to get "AAAAABBA". The substring "AAAA" has length 4.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

For every possible substring, count the frequency of each character and determine how many replacements are needed to make all characters the same. The number of replacements needed is the window length minus the count of the most frequent character in that window. If this is at most k, the substring is valid. We track the maximum length among all valid substrings.

Algorithm

  1. Initialize maxLen to 0.
  2. For each starting index i, iterate over each ending index j from i to n - 1.
  3. Maintain a frequency count of characters in the window [i, j].
  4. Find the maximum frequency character count in the current window.
  5. If (j - i + 1) - maxFreq <= k, update maxLen with the window size.
  6. Return maxLen.
TimeO(n^2)SpaceO(1) since the frequency array has at most 26 entries

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxLen = 0;
        int n = s.size();

        for (int i = 0; i < n; i++) {
            int freq[26] = {};
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                freq[s[j] - 'A']++;
                maxFreq = max(maxFreq, freq[s[j] - 'A']);
                if ((j - i + 1) - maxFreq <= k) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }

        return maxLen;
    }
};
Java 21
class Solution {
    public int characterReplacement(String s, int k) {
        int maxLen = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'A']++;
                maxFreq = Math.max(maxFreq, freq[s.charAt(j) - 'A']);
                if ((j - i + 1) - maxFreq <= k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }

        return maxLen;
    }
}
Python 3.12
def characterReplacement(s: str, k: int) -> int:
    max_len = 0
    n = len(s)

    for i in range(n):
        freq = {}
        max_freq = 0
        for j in range(i, n):
            freq[s[j]] = freq.get(s[j], 0) + 1
            max_freq = max(max_freq, freq[s[j]])
            if (j - i + 1) - max_freq <= k:
                max_len = max(max_len, j - i + 1)

    return max_len
Go 1.26
func characterReplacement(s string, k int) int {
    maxLen := 0
    n := len(s)

    for i := 0; i < n; i++ {
        freq := [26]int{}
        maxFreq := 0
        for j := i; j < n; j++ {
            freq[s[j]-'A']++
            if freq[s[j]-'A'] > maxFreq {
                maxFreq = freq[s[j]-'A']
            }
            if (j-i+1)-maxFreq <= k {
                if j-i+1 > maxLen {
                    maxLen = j - i + 1
                }
            }
        }
    }

    return maxLen
}
Approach 2

Sliding Window

Intuition

We use a sliding window that expands to the right and contracts from the left. We maintain a frequency count of characters in the window and track the count of the most frequent character (maxFreq). The window is valid when the number of characters to replace, which is windowLength - maxFreq, is at most k. When the window becomes invalid, we shrink it from the left. A key optimization is that maxFreq never needs to decrease -- we only care about finding longer valid windows, and a longer valid window requires maxFreq to be at least as large.

Algorithm

  1. Initialize a frequency array of size 26, left = 0, maxFreq = 0, and maxLen = 0.
  2. Expand the window by moving right from 0 to n - 1.
  3. Increment the frequency of s[right] and update maxFreq if this character now has the highest frequency.
  4. While the window is invalid ((right - left + 1) - maxFreq > k), decrement the frequency of s[left] and increment left.
  5. Update maxLen with the current window size right - left + 1.
  6. Return maxLen.
TimeO(n)SpaceO(1) since the frequency array has at most 26 entries

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int characterReplacement(string s, int k) {
        int freq[26] = {};
        int maxFreq = 0;
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.size(); right++) {
            freq[s[right] - 'A']++;
            maxFreq = max(maxFreq, freq[s[right] - 'A']);

            while ((right - left + 1) - maxFreq > k) {
                freq[s[left] - 'A']--;
                left++;
            }

            maxLen = max(maxLen, right - left + 1);
        }

        return maxLen;
    }
};
Java 21
class Solution {
    public int characterReplacement(String s, int k) {
        int[] freq = new int[26];
        int maxFreq = 0;
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            freq[s.charAt(right) - 'A']++;
            maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'A']);

            while ((right - left + 1) - maxFreq > k) {
                freq[s.charAt(left) - 'A']--;
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}
Python 3.12
def characterReplacement(s: str, k: int) -> int:
    freq = {}
    max_freq = 0
    max_len = 0
    left = 0

    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1
        max_freq = max(max_freq, freq[s[right]])

        while (right - left + 1) - max_freq > k:
            freq[s[left]] -= 1
            left += 1

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

    return max_len
Go 1.26
func characterReplacement(s string, k int) int {
    freq := [26]int{}
    maxFreq := 0
    maxLen := 0
    left := 0

    for right := 0; right < len(s); right++ {
        freq[s[right]-'A']++
        if freq[s[right]-'A'] > maxFreq {
            maxFreq = freq[s[right]-'A']
        }

        for (right-left+1)-maxFreq > k {
            freq[s[left]-'A']--
            left++
        }

        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }

    return maxLen
}

Frequently asked questions

What is the optimal time complexity of Longest Repeating Character Replacement?

The most efficient approach in this guide ("Sliding Window") runs in O(n) time and uses O(1) since the frequency array has at most 26 entries extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Longest Repeating Character Replacement use?

Longest Repeating Character Replacement is a medium-level Sliding Window problem involving String, Sliding Window, Hash Table. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Longest Repeating Character Replacement be solved without extra space?

The most space-efficient approach in this guide uses O(1) since the frequency array has at most 26 entries extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1) since the frequency array has at most 26 entries, while the optimized version uses O(1) since the frequency array has at most 26 entries.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Longest Substring Without Repeating Characters

Original problem: leetcode.com

Loading editor...
Input
s=
"ABAB"
k=
2
Expected Output
4