Longest Repeating Character Replacement solution and explanation
Infosys
Google
9 more videos on this problem
Longest Repeating Character Replacement - Leetcode 424 - PythonNeetCode · 20:44 · 821K views
LeetCode Longest Repeating Character Replacement Solution Explained - JavaNick White · 11:43 · 77K views
Longest Repeating Character Replacement (LeetCode 424) | Single iteration | Sliding WindowNikhil Lohia · 18:04 · 41K views
Longest Repeating Character Replacement - Leetcode 424 - Sliding Window (Python)Greg Hogg · 13:29 · 39K views
[Animated] LeetCode 424 Longest Repeating Character Replacement | Blind 75 | Sliding WindowCode In Motion · 11:49 · 11K views
[Java] Leetcode 424. Longest Repeating Character Replacement [Sliding Window #6]Eric Programming · 13:58 · 11K views
Google Coding Interview Question - Longest Repeating Character Replacement (Leetcode 424)Algorithms Casts · 17:18 · 6K views
LeetCode 424. Longest Repeating Character ReplacementHappy Coding · 15:14 · 4K views
Longest Repeating Character Replacement - 424. LeetCode - JavaTeddy Smith · 15:38 · 2K views
Longest Repeated Character Replacement - Amazon Interview QuestionAlgoJS · 8:07 · 7K views
The problem
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 <= 105sconsists 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.
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = [0] * 26
left = 0
maxFreq = 0
maxLength = 0
for right in range(len(s)):
count[ord(s[right]) - ord('A')] += 1
maxFreq = max(maxFreq, count[ord(s[right]) - ord('A')])
if right - left + 1 - maxFreq > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
maxLength = max(maxLength, right - left + 1)
return maxLength
# Example usage:
solution = Solution()
print(solution.characterReplacement("AABABBA", 1)) # Output: 4public class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int left = 0, maxFreq = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
count[s.charAt(right) - 'A']++;
maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);
if (right - left + 1 - maxFreq > k) {
count[s.charAt(left) - 'A']--;
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.characterReplacement("AABABBA", 1)); // Output: 4
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int characterReplacement(string s, int k) {
int left = 0, right = 0, maxFreq = 0, maxLength = 0;
vector<int> count(26, 0);
while (right < s.size()) {
count[s[right] - 'A']++;
maxFreq = max(maxFreq, count[s[right] - 'A']);
if (right - left + 1 - maxFreq > k) {
count[s[left] - 'A']--;
left++;
}
maxLength = max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
int main() {
string s = "AABABBA";
int k = 1;
cout << characterReplacement(s, k) << endl; // Output: 4
return 0;
}function characterReplacement(s, k) {
const count = new Array(26).fill(0);
let left = 0, maxFreq = 0, maxLength = 0;
for (let right = 0; right < s.length; right++) {
count[s.charCodeAt(right) - 65]++;
maxFreq = Math.max(maxFreq, count[s.charCodeAt(right) - 65]);
if (right - left + 1 - maxFreq > k) {
count[s.charCodeAt(left) - 65]--;
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
console.log(characterReplacement("AABABBA", 1)); // Output: 4;#include <stdio.h>
#include <string.h>
int characterReplacement(char * s, int k){
int left = 0, right = 0, maxFreq = 0, maxLen = 0;
int freq[26] = {0};
while (s[right] != '\0') {
freq[s[right] - 'A']++;
maxFreq = (freq[s[right] - 'A'] > maxFreq) ? freq[s[right] - 'A'] : maxFreq;
if (right - left + 1 - maxFreq > k) {
freq[s[left] - 'A']--;
left++;
}
maxLen = (right - left + 1) > maxLen ? (right - left + 1) : maxLen;
right++;
}
return maxLen;
}
int main() {
char s[] = "AABABBA";
int k = 1;
printf("%d\n", characterReplacement(s, k)); // Output: 4
return 0;
}public class Solution {
public int CharacterReplacement(string s, int k) {
int[] count = new int[26];
int left = 0, maxFreq = 0, maxLength = 0;
for (int right = 0; right < s.Length; right++) {
count[s[right] - 'A']++;
maxFreq = Math.Max(maxFreq, count[s[right] - 'A']);
if (right - left + 1 - maxFreq > k) {
count[s[left] - 'A']--;
left++;
}
maxLength = Math.Max(maxLength, right - left + 1);
}
return maxLength;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.CharacterReplacement("AABABBA", 1)); // Output: 4
}
}We track character counts using a fixed-size list count and adjust windows based on the maximum character frequency. The solution calculates maximum substring length by ensuring the number of different characters (changes) doesn't exceed k.
This solution runs in O(n) time and uses O(1) space, as the list for frequency counting is of constant size.
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.
function characterReplacement(s: string, k: number): number {
const idx = (c: string) => c.charCodeAt(0) - 65;
const cnt: number[] = Array(26).fill(0);
const n = s.length;
let [l, mx] = [0, 0];
for (let r = 0; r < n; ++r) {
mx = Math.max(mx, ++cnt[idx(s[r])]);
if (r - l + 1 - mx > k) {
--cnt[idx(s[l++])];
}
}
return n - l;
}func characterReplacement(s string, k int) int {
cnt := [26]int{}
l, mx := 0, 0
for r, c := range s {
cnt[c-'A']++
mx = max(mx, cnt[c-'A'])
if r-l+1-mx > k {
cnt[s[l]-'A']--
l++
}
}
return len(s) - l
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Count | This solution runs in O(n) time and uses O(1) space, as the list for frequency counting is of constant size. |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Frequency Count | O(n²) | O(1) | Useful for understanding the replacement condition and verifying logic on small inputs. |
| Sliding Window with Frequency Count | O(n) | O(1) | Optimal approach for interviews and production. Processes each character once using two pointers. |
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.