Data Structures & Algorithms (Sliding Window): Longest Repeating Character Replacement

February 3, 2026

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.

Playground: Leetcode 424

Key Observations

A few key questions that need to be addressed are:

Q1. What is the minimum number of replacements required to make all characters in a substring the same?

The minimum number of replacements required to make all characters in a substring the same is (length of substring - frequency of the most frequent character).

For example: If we want to convert the entire string "AABBAC" into a substring containing the same letter, the minimum number of replacements required is 3, achieved by keeping A, i.e., the most frequent character.

Target characterCharacters to replaceReplacements
AB B C3
BA A A C4
CA A B B A5
Q2. What makes a substring eligible for conversion?

A substring is eligible to be converted into a substring containing the same letter if the minimum number of replacements required is <= k.

For example:

key-observations

Naive Approach - Nested Loops

Iterate over every substring in s, check if it is eligible to be converted into a substring containing the same letter, and keep track of the longest eligible substring observed.

Algorithm

1. Iterate over each character in "s", treating it as the starting position of a substring.
2. For each starting position, initialize a frequency map to track the character in the current 
   substring.
3. Expand the substring one character at a time towards the right. Update the frequency of each 
   newly added character.
4. For the current substring, check if the number of replacements required is <= k.
5. Update the longest eligible substring if necessary.
6. Return the length of the longest eligible substring.

Implementation

Sample inputs
1public static int characterReplacement(String s, int k) {
2
3 // 1. Initialize a variable to store the length of the longest substring found so far.
4 int longestSubstringLength = 0;
5
6 // 2. Iterate over each character in "s"
7 for (int i = 0; i < s.length(); i++) {
8
9 // 3. Initialize a frequency map to track the character in the current substring.
10 Map<Character, Integer> frequencyMap = new HashMap<>();
11
12 // 4. Initialize a variable to store the frequency of most frequent character in the current substring.
13 int mostFrequentCharacterFrequency = 0;
14
15 // 5. Expand the current substring one character at a time.
16 for (int j = i; j < s.length(); j++) {
17
18 // 6. Update the frequency of the current character.
19 char ch = s.charAt(j);
20 int currentCharacterFrequency = frequencyMap.getOrDefault(ch, 0) + 1;
21 frequencyMap.put(ch, currentCharacterFrequency);
22
23 // 7. Update the frequency of the most frequent character, if necessary.
24 mostFrequentCharacterFrequency = Math.max(mostFrequentCharacterFrequency, currentCharacterFrequency);
25
26 // 8. Check if the current substring is eligible.
27 int currentSubstringLength = j - i + 1;
28 if (currentSubstringLength - mostFrequentCharacterFrequency <= k) {
29
30 // 9. Update the length of the longest eligible substring, if necessary.
31 longestSubstringLength = Math.max(longestSubstringLength, currentSubstringLength);
32 }
33
34 }
35
36 }
37
38 // 10. Return the length of the longest eligible substring.
39 return longestSubstringLength;
40
41}
k2
Input string s
j
j
j
j
A
B
A
B
i
i
i
i
0
1
2
3
Current substring—
s[i..j]len —
replacements —
frequencyMap
Empty
i = —
j = —
mostFrequentCharacterFrequency = —
longestSubstringLength0
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/64

Time Complexity

The outer loop runs n times, where n = s.length(). For the ith iteration of the outer loop, the inner loop runs (n - i) iterations.

Since each operation performed inside the inner loop takes constant time, i.e., O(1). Therefore, the total number of operations performed is proportional to:

(n - 0) + (n - 1) + (n - 2) + ... + (n - (n - 1)) = n + (n - 1) + (n - 2) + ... + 1
                                                  = n(n + 1) / 2

Since the total number of operations is of the order of n², the overall time complexity is O(n²).

Space Complexity

We use a HashMap to store the frequency of each character in current substring.

In the worst case, when all characters in s are unique, the HashMap can contain upto n distinct characters simnultaneously, where n = s.length().

Therefore, the overall time complexity is O(n).

Key Optimizations

For any starting character ch, we expand the substring towards the right. If, at some point, the current substring becomes ineligible, adding more characters to the right cannot make it eligible again.

For the next starting character, we also don't need to restart the exploration from the beginning. All smaller substrings contained between the new starting position and the previous stopping position cannot give us a longer answer. We can continue expanding from the position where the previous exploration ended.

key-optimizations

Suitable Approach - Sliding Window Technique

Maintain a single window using two pointers: left (marks the start of the current window) and right (marks the end of the current window).

Instead of restarting the inner loop for every starting position, expand right and move left forward whenever the current window becomes ineligible.

Algorithm

1. Initialize:
   a. A variable "longestSubstringLength" to track the length of the longest eligible substring
      found so far.
   b. A variable "mostFrequentCharacterFrequency" to track the frequency of the most frequent 
      character in the current window.
   c. Two pointers "left" and "right" to represent the boundaries of the current window.
   d. A frequency map "frequencyMap" to track the frequency of each characters present in the 
      current window.

2. Start expanding "right" one character at a time: 
   a. Update the frequency of the newly added character in "frequencyMap".
   b. Update "mostFrequentCharacterFrequency" if necessary.
   c. While the current substring is ineligible:
      i.  Increment "left" to shrink the window.
      ii. Update the frequency of the character removed from the window.
   d. Once the window is eligible, update "longestSubstringLength" if necessary.

3. Return "longestSubstringLength".

Implementation

Sample inputs
1public int characterReplacement(String s, int k) {
2
3 // 1. Initialize
4 int longestSubstringLength = 0;
5 int mostFrequentCharacterFrequency = 0;
6 int left = 0, right = 0;
7
8 Map<Character, Integer> frequencyMap = new HashMap<>();
9
10 // 2. Expand "right" one character at a time
11 while (right < s.length()) {
12
13 // a. Update the frequency of the newly added character
14 char newCh = s.charAt(right);
15
16 int currentCharacterUpdatedFrequency =
17 frequencyMap.getOrDefault(newCh, 0) + 1;
18
19 frequencyMap.put(newCh, currentCharacterUpdatedFrequency);
20
21 // b. Update the frequency of the most frequent character
22 mostFrequentCharacterFrequency =
23 Math.max(
24 mostFrequentCharacterFrequency,
25 currentCharacterUpdatedFrequency
26 );
27
28 // c. While the current window is ineligible, shrink it
29 while (right - left + 1 - mostFrequentCharacterFrequency > k) {
30
31 char oldCh = s.charAt(left);
32
33 // i. Decrease the frequency of the character
34 // removed from the window.
35 frequencyMap.put(oldCh, frequencyMap.get(oldCh) - 1);
36
37 // ii. Move the left pointer forward.
38 left++;
39 }
40
41 // d. The current window is now eligible.
42 // Update the longest eligible substring.
43 longestSubstringLength =
44 Math.max(
45 longestSubstringLength,
46 right - left + 1
47 );
48
49 // Move right to expand the window.
50 right++;
51 }
52
53 // 3. Return the length of the longest eligible substring.
54 return longestSubstringLength;
55
56}
k2
Input string s
right
right
right
right
A
B
A
B
left
left
left
left
0
1
2
3
Current window—
s[left..right]len —
replacements —
frequencyMap
Empty
left = —
right = —
mostFrequentCharacterFrequency = 0
longestSubstringLength0
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/22

Time complexity

The checks and updates performed at each step take contant time. Hence, the time complexity is dependent on the number of times the left and right pointers move.

Both left and right pointers only move forward. The right pointer increments exactly n times. The left pointer moves at most n times over the entire life of the algorithm.

Because each pointer traverses the string at most once, the total index movements are bounded by 2n. Hence, the overall time complexity is O(2n) ~ O(n).

Space Complexity

In the worst case, when all characters in s are distinct, the frequencyMap can store the frequency of all n characters simnultaneously.

Since the space required by the frequencyMap is bounded by n, the overall space complexity is O(n).