Skip to main content
Talentd

Longest Repeating Character Replacement - Solution & Explanation

MediumHash TableStringSliding Window15 min readAsked at: Amazon, Microsoft, Apple +19
Practice this problem

Problem Statement

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 <= 105
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length

Approach Overview

Problem Overview: Given a string s containing uppercase English letters and an integer k, find the length of the longest substring you can convert into a string of identical characters by replacing at most k characters. The goal is to maximize the window length while ensuring no more than k replacements are required.

Approach 1: Brute Force with Frequency Counting (O(n²) time, O(1) space)

Start every substring at index i and extend it one character at a time to index j. Maintain a frequency array for the 26 uppercase characters and track the most frequent character inside the current substring. The number of replacements needed is (window_length - max_frequency). If this value exceeds k, the substring becomes invalid. Although the character set is fixed so the frequency array uses constant space, evaluating all substrings leads to O(n²) time. This method helps build intuition but is too slow for large inputs.

Approach 2: Sliding Window with Frequency Count (O(n) time, O(1) space)

The optimal solution uses a variable-length window with two pointers. Expand the right pointer while updating a frequency array that tracks counts of characters inside the window. Keep a variable maxFreq representing the highest frequency of any character in the current window. The number of replacements required to make the window uniform is window_size - maxFreq. If this exceeds k, shrink the window by moving the left pointer and updating the counts.

The key insight: the window is valid when (right - left + 1) - maxFreq ≤ k. Because the alphabet size is fixed, frequency updates are constant time. Each character enters and leaves the window at most once, producing linear O(n) time. Space remains O(1) due to the fixed-size frequency array. This technique is a classic pattern combining sliding window mechanics with a small hash table or array for counts while scanning a string.

One subtle optimization keeps maxFreq as the historical maximum rather than recomputing it every time the window shrinks. Even if it becomes slightly outdated, the window size constraint still guarantees correctness because the algorithm only expands when a valid window exists. This avoids scanning the entire frequency array repeatedly.

Recommended for interviews: The sliding window with frequency count is the expected solution. Interviewers want to see you recognize the pattern where a window expands greedily and shrinks when a constraint breaks. Mentioning the brute-force approach briefly shows understanding of the problem space, but implementing the O(n) sliding window demonstrates mastery of window-based string problems.

Approach 1: Sliding Window with Frequency Count

This approach is based on using a sliding window to track the current substring and its character frequencies. Within the window, we maintain the frequency of each character and focus on the most frequent character. By using this information, we determine how many changes are needed to make all characters in the window the same. We adjust the window size based on whether the number of changes required exceeds k.

We initialize two pointers, left and right, to maintain the window. The frequency of each character in the current window is stored in an array freq. As we expand the window by moving right, we update the frequency count, checking if the current window size minus the maximum frequency is greater than k. If so, we move left to reduce the window size. Finally, we calculate the maximum length of the substring observed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n), where n is the length of string s, as we pass over the string with two pointers. Space complexity is O(1) since the frequency array size does not depend on the input size but on the fixed size of the English alphabet.

Try this approach in the editor →

Approach 2: Two Pointers

We use a hash table cnt to count the occurrence of each character in the string, and two pointers l and r to maintain a sliding window, such that the size of the window minus the count of the most frequent character does not exceed k.

We iterate through the string, updating the right boundary r of the window each time, updating the count of characters within the window, and updating the maximum count mx of the characters that have appeared. When the size of the window minus mx is greater than k, we need to shrink the left boundary l of the window, updating the count of characters within the window, until the size of the window minus mx is no longer greater than k.

Finally, the answer is n - l, where n is the length of the string.

The time complexity is O(n), and the space complexity is O(|\Sigma|). Where n is the length of the string, and |\Sigma| is the size of the character set. In this problem, the character set is uppercase English letters, so |\Sigma| = 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window with Frequency Count

The time complexity is O(n), where n is the length of string s, as we pass over the string with two pointers. Space complexity is O(1) since the frequency array size does not depend on the input size but on the fixed size of the English alphabet.

Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Frequency CountO(n²)O(1)Useful for understanding the replacement condition and verifying logic on small inputs.
Sliding Window with Frequency CountO(n)O(1)Optimal approach for interviews and production. Processes each character once using two pointers.

Video Solution

Longest Repeating Character Replacement - Leetcode 424 - Python • NeetCode • 821,153 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Repeating Character Replacement easy or hard?
The problem is classified as Medium on LeetCode. The difficulty comes from recognizing the sliding window invariant: the window stays valid while replacements needed are at most k. Once that condition is clear, the implementation becomes straightforward.
Longest Repeating Character Replacement Python/Java solution
Most implementations use a sliding window with a 26-length frequency array. Python typically uses a list for counts, while Java and C++ use integer arrays. The algorithm expands the right pointer, updates counts, and shrinks the window whenever more than k replacements are needed.
How to solve Longest Repeating Character Replacement in O(n)?
Use a sliding window with two pointers. Track character counts inside the window and maintain the maximum frequency of any character. If (window size − max frequency) becomes greater than k, move the left pointer to shrink the window. Continue expanding the right pointer and update the maximum valid window length.
What is the best approach for Longest Repeating Character Replacement?
The optimal approach is a sliding window with a frequency count of characters. Maintain a window and track the most frequent character inside it. The window is valid if (window length − max frequency) ≤ k. This method runs in O(n) time and O(1) space because the alphabet size is fixed.
Is Longest Repeating Character Replacement asked at Google/Amazon/Meta?
Longest Repeating Character Replacement is a common sliding window interview problem reported in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests understanding of two‑pointer techniques, frequency counting, and maintaining window constraints efficiently.
What data structure is used in Longest Repeating Character Replacement?
A frequency array or hash table is used to store counts of characters inside the current window. Because the string contains only uppercase English letters, a fixed array of size 26 is typically used, providing constant-time updates and lookups.
What is the time complexity of Longest Repeating Character Replacement?
The optimal sliding window solution runs in O(n) time where n is the length of the string. Each character is added to and removed from the window at most once. Space complexity is O(1) since only a fixed array of size 26 is required for character frequencies.

Ready to solve this problem?

Practice Longest Repeating Character Replacement with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring of One Repeating Character

Next

Longest Substring with At Most K Distinct Characters