Longest Repeating Character Replacement - Sliding Window - Visualization - Visualization

Sliding Window & Two Pointer Problems

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

You are given a string s consisting of only uppercase English letters and an integer k. You can replace at most k characters in the string so that all characters in the substring are the same.

Return the length of the longest substring containing the same letter you can get after performing at most k character replacements.

Example:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the second 'B' with 'A' to get "AABABA" → Longest same-letter substring is "AAAA".

Examples❯

s k Output Description
"AABABBA" 1 4 Replace one 'B' with 'A' to get "AABABA" → longest substring is "AAAA"
"ABAB" 2 4 Replace both 'B' with 'A' to get "AAAA"
"AABABBA" 0 2 No replacements allowed; longest same-letter substring is "AA"
"AAAA" 2 4 All characters are the same; no replacements needed
"ABCDE" 1 2 Can only replace 1 character; best case is two identical letters like "AA"
"AAAB" 1 4 Replace 'B' with 'A' to get "AAAA"
"BAAA" 0 3 No replacements allowed; "AAA" is the longest same-letter substring
"" 2 0 Empty string; no substrings possible
"A" 0 1 Single character string; always length 1
"ABBB" 2 4 Replace 'A' and one 'B' if needed to make "BBBB"

Solution❯

Understanding the Problem

We are given a string s that contains only uppercase English letters and an integer k. Our task is to find the length of the longest substring where we can change at most k characters so that all characters in that substring become the same.

This is a classic sliding window problem. The goal is to find a window (substring) that, after making at most k changes, becomes a block of repeating characters.

Intuition: If we know how many times the most frequent character appears in our current window, and the remaining characters can be changed within k operations, then this window is valid.

Step-by-Step Solution with Example

Step 1: Initialize Variables

We keep a frequency array (or hashmap) to count characters in the current window. We'll use two pointers left and right to create a sliding window. Also, track maxCount, which is the frequency of the most frequent character in the window.

Step 2: Iterate with Right Pointer

We expand the window by moving right. For each character, we update its count and check if the window is still valid. A window is valid if:

(window length) - (maxCount) <= k

This condition tells us if we can convert all other characters to the most frequent one within k changes.

Step 3: Shrink the Window if Invalid

If the condition is not met, we shrink the window from the left and update frequencies accordingly.

Step 4: Track the Maximum Length

At each step, update maxLen with the size of the current valid window.

Example:

s = "AABABBA", k = 1

  1. Start with left = 0, right = 0, window = "A", maxCount = 1 → valid → maxLen = 1
  2. right = 1 → window = "AA", maxCount = 2 → valid → maxLen = 2
  3. right = 2 → window = "AAB", maxCount = 2 → (3 - 2 = 1) ≤ k → valid → maxLen = 3
  4. right = 3 → window = "AABA", maxCount = 3 → (4 - 3 = 1) ≤ k → valid → maxLen = 4
  5. right = 4 → window = "AABAB", maxCount = 3 → (5 - 3 = 2) > k → invalid → move left to 1 → window = "ABAB"
  6. window becomes valid again → maxLen still 4
  7. right = 5 → window = "ABABB", maxCount = 3 → (5 - 3 = 2) > k → move left to 2 → window = "BABB"
  8. still invalid → move left to 3 → window = "ABB"
  9. right = 6 → window = "ABBA", maxCount = 2 → (4 - 2 = 2) > k → move left to 4 → window = "BBA"

Answer remains 4 for the window "AABA"

Edge Cases

  • All characters same: No need to replace anything, so answer is length of the string. Example: s = "AAAA", k = 2 → Output: 4
  • No characters to replace (k = 0): Just look for the longest block of identical characters. Example: s = "ABAB", k = 0 → Output: 1
  • Empty string: s = "", k = 2 → Output: 0
  • k greater than string length: Can convert entire string. Example: s = "ABC", k = 5 → Output: 3

Final Thoughts

This problem is an excellent example of the sliding window technique. By keeping track of the most frequent character in the current window and adjusting the window when necessary, we ensure an efficient solution that runs in linear time. The key idea is that we don't need to actually perform replacements — just count if we could do it within k changes.

Always test with edge cases like empty strings, k = 0, and strings with all the same characters to validate your logic.

Algorithm Steps❯

  1. Initialize an array freq[26] to count character frequencies in the current window.
  2. Use two pointers: left and right to define the window bounds.
  3. Track maxCount, the count of the most frequent character in the current window.
  4. Initialize maxLen = 0 to store the maximum window length that meets the condition.
  5. Loop right from 0 to length of string:
  6. → Increment freq[s[right]] and update maxCount if needed.
  7. → If window length - maxCount > k, shrink the window by incrementing left and decrementing freq[s[left]].
  8. → Update maxLen = max(maxLen, right - left + 1).
  9. After the loop, return maxLen as the result.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <string.h>

int characterReplacement(char* s, int k) {
    int freq[26] = {0};
    int left = 0, right = 0;
    int maxCount = 0, maxLen = 0;
    int len = strlen(s);

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

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

        if ((right - left + 1) > maxLen) {
            maxLen = right - left + 1;
        }
    }

    return maxLen;
}

int main() {
    char s[] = "AABABBA";
    int k = 1;
    int result = characterReplacement(s, k);
    printf("%d\n", result); // 4
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)The sliding window expands and contracts across the entire string exactly once. Each character is processed at most twice — once when expanding the window and once when shrinking it — making the overall time linear.
Average CaseO(n)In a typical scenario, the window slides through the string while maintaining frequency counts. Each character is added and removed from the window at most once, resulting in linear time complexity.
Worst CaseO(n)Even in the worst case, where the window frequently contracts due to exceeding the allowed replacement count, the left and right pointers move from start to end only once. This gives a linear time complexity.

Space Complexity❯

O(1)

Explanation: The algorithm uses a fixed-size array of 26 integers to count character frequencies and a few additional integer variables. This constant space usage does not depend on input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...