Longest Repeating Character Replacement

13 May 2026 0 Likes

Problem Description

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

Return the length of the longest substring containing the same letter you can obtain after performing at most k replacements.
Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: We can replace the two 'A' characters with 'B' or the two 'B' characters with 'A'. The entire string becomes a repeating-character substring of length: 4
Example 2:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: One possible transformation is: "AABBBBA". The substring: "BBBB" has length: 4
Example 3:
Input: s = "AAAA", k = 2
Output: 4
Explanation: The string already contains repeating characters, so no replacement is required.

Constraints

1. The string contains only uppercase English letters.
2. You may perform at most k character replacements.
3. The output should represent the length of the longest valid repeating-character substring.
4. The length of the string may vary depending on platform limits.
Efficient solutions are expected to process the string in linear time.

Understanding the Problem

The problem asks us to find the longest contiguous substring that can be converted into a string containing only one repeating character using at most k replacements.

For example, consider: s = "AABABBA" and k = 1.

If we examine the substring "AABA", the character 'A' appears most frequently. By replacing the single 'B' with 'A', the substring becomes "AAAA", which is a valid repeating-character substring of length 4.

The key observation is that, for any valid window, we only need to replace the characters that differ from the most frequent character in that window. Therefore, if: Window Length - Maximum Character Frequency ≤ k, then the current substring can be transformed into a valid repeating-character substring.

Hints

The first hint is to think about maintaining a dynamic window instead of checking every possible substring separately. A sliding window technique works efficiently because the substring must remain contiguous.

Inside the current window, track the frequency of every character and continuously maintain the count of the most frequent character.

If the number of characters needing replacement becomes greater than k, shrink the window from the left side until the window becomes valid again.

While expanding and shrinking the window, continuously update the maximum valid window length.

Solutions

BETTER

Sliding Window with HashMap Frequency Tracking Solution

This approach uses the sliding window technique along with a HashMap to track character frequencies within the current window. The main idea is to maintain the longest valid substring in which at most k characters need to be replaced.

As the right pointer expands the window, we increase the frequency count of the current character in the map. Simultaneously, we track the frequency of the most frequent character in the current window using: maxCount.

The number of replacements required for the current window is calculated as: Window Length - maxCount, because all other characters in the window must be replaced with the most frequent character.

If this value becomes greater than k, the current window becomes invalid. In that case, we shrink the window from the left by decreasing the frequency of the leftmost character and moving the left pointer forward.

Throughout the traversal, we continuously update the maximum valid window length found so far.
public class A_SlidingWindowAndMap {
    public int characterReplacement(String s, int k) {
        Map<Character, Integer> count = new HashMap<>();

        int left = 0;
        int maxCount = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);

            count.put(
                    rightChar,
                    count.getOrDefault(rightChar, 0) + 1
            );

            maxCount = Math.max(
                    maxCount,
                    count.get(rightChar)
            );

            if ((right - left + 1) - maxCount > k) {
                char leftChar = s.charAt(left);

                count.put(
                        leftChar,
                        count.get(leftChar) - 1
                );

                left++;
            }

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

        return maxLength;
    }
}
class Solution:
    def characterReplacement(self, s, k):
        count = {}

        left = 0
        max_count = 0
        max_length = 0

        for right in range(len(s)):
            right_char = s[right]

            count[right_char] = (
                count.get(right_char, 0) + 1
            )

            max_count = max(
                max_count,
                count[right_char]
            )

            if (right - left + 1) - max_count > k:
                left_char = s[left]

                count[left_char] -= 1

                left += 1

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

        return max_length
Time Complexity
O(n)
Space Complexity
O(1)

(Because only uppercase English letters are used)
OPTIMAL

Sliding Window with Frequency Array Solution

This approach further optimizes the previous solution by replacing the HashMap with a fixed-size frequency array. Since the string contains only uppercase English letters, an array of size 26 is sufficient to track character frequencies.

The sliding window logic remains the same. As the right pointer expands the window, we increase the frequency of the current character in the array while continuously maintaining: maxCount, which stores the frequency of the most frequently occurring character within the current window.

The number of replacements required for the current window is calculated as: Window Length - maxCount.

If this value exceeds k, the window becomes invalid, so we shrink it from the left by decreasing the frequency of the leftmost character and moving the left pointer forward.

Because array access is faster than HashMap operations, this implementation offers better practical performance while preserving the same overall logic and time complexity.
public class A_SlidingWindowAndArray {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];

        int left = 0;
        int maxCount = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);

            count[rightChar - 'A'] =
                    count[rightChar - 'A'] + 1;

            maxCount = Math.max(
                    maxCount,
                    count[rightChar - 'A']
            );

            if ((right - left + 1) - maxCount > k) {
                char leftChar = s.charAt(left);

                count[leftChar - 'A'] =
                        count[leftChar - 'A'] - 1;

                left++;
            }

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

        return maxLength;
    }
}
class Solution:
    def characterReplacement(self, s, k):
        count = [0] * 26

        left = 0
        max_count = 0
        max_length = 0

        for right in range(len(s)):
            right_char = s[right]

            count[ord(right_char) - ord('A')] += 1

            max_count = max(
                max_count,
                count[ord(right_char) - ord('A')]
            )

            if (right - left + 1) - max_count > k:
                left_char = s[left]

                count[ord(left_char) - ord('A')] -= 1

                left += 1

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

        return max_length
Time Complexity
O(n)
Space Complexity
O(1)

Conclusion

The Longest Repeating Character Replacement problem is an important sliding window problem that teaches how to maintain dynamic constraints while traversing a string. The problem demonstrates how frequency tracking and window resizing can efficiently optimize substring-related problems.

Mastering this problem helps build a strong understanding of sliding window optimization, frequency counting, and dynamic substring processing, which are commonly used in coding interviews and real-world text processing applications.

💬 Comments