Longest Repeating Character Replacement using Sliding Window

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".

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.

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.

#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;
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int characterReplacement(const string& s, int k) {
    vector<int> freq(26, 0);
    int left = 0, maxCount = 0, maxLen = 0;

    for (int right = 0; right < (int)s.size(); ++right) {
        freq[s[right] - 'A']++;
        maxCount = max(maxCount, freq[s[right] - 'A']);

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

        maxLen = max(maxLen, right - left + 1);
    }

    return maxLen;
}

int main() {
    string s = "AABABBA";
    int k = 1;
    cout << characterReplacement(s, k) << endl; // 4
    return 0;
}

def characterReplacement(s: str, k: int) -> int:
    freq = [0] * 26
    left = 0
    maxCount = 0
    maxLen = 0

    for right in range(len(s)):
        freq[ord(s[right]) - ord('A')] += 1
        maxCount = max(maxCount, freq[ord(s[right]) - ord('A')])

        while (right - left + 1) - maxCount > k:
            freq[ord(s[left]) - ord('A')] -= 1
            left += 1

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

    return maxLen

# Example usage
s = "AABABBA"
k = 1
print(characterReplacement(s, k))  # 4

public class LongestRepeatingCharReplacement {
    public static int characterReplacement(String s, int k) {
        int[] freq = new int[26];
        int left = 0, maxCount = 0, maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            freq[s.charAt(right) - 'A']++;
            maxCount = Math.max(maxCount, freq[s.charAt(right) - 'A']);

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

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

        return maxLen;
    }

    public static void main(String[] args) {
        String s = "AABABBA";
        int k = 1;
        System.out.println(characterReplacement(s, k)); // 4
    }
}

function characterReplacement(s, k) {
  const freq = new Array(26).fill(0);
  let left = 0, maxCount = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    freq[s.charCodeAt(right) - 65]++;
    maxCount = Math.max(maxCount, freq[s.charCodeAt(right) - 65]);

    while ((right - left + 1) - maxCount > k) {
      freq[s.charCodeAt(left) - 65]--;
      left++;
    }

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

  return maxLen;
}

// Example usage
const s = "AABABBA";
const k = 1;
console.log(characterReplacement(s, k)); // 4

package main

import "fmt"

func characterReplacement(s string, k int) int {
    freq := make([]int, 26)
    left, maxCount, maxLen := 0, 0, 0

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

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

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

    return maxLen
}

func main() {
    s := "AABABBA"
    k := 1
    fmt.Println(characterReplacement(s, k)) // 4
}

fn character_replacement(s: &str, k: usize) -> usize {
    let mut freq = [0; 26];
    let (mut left, mut max_count, mut max_len) = (0, 0, 0);
    let s_bytes = s.as_bytes();

    for right in 0..s.len() {
        freq[(s_bytes[right] - b'A') as usize] += 1;
        max_count = max_count.max(freq[(s_bytes[right] - b'A') as usize]);

        while (right - left + 1) - max_count > k {
            freq[(s_bytes[left] - b'A') as usize] -= 1;
            left += 1;
        }

        max_len = max_len.max(right - left + 1);
    }

    max_len
}

fn main() {
    let s = "AABABBA";
    let k = 1;
    println!("{}", character_replacement(s, k)); // 4
}

fun characterReplacement(s: String, k: Int): Int {
    val freq = IntArray(26)
    var left = 0
    var maxCount = 0
    var maxLen = 0

    for (right in s.indices) {
        freq[s[right] - 'A']++
        maxCount = maxOf(maxCount, freq[s[right] - 'A'])

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

        maxLen = maxOf(maxLen, right - left + 1)
    }

    return maxLen
}

fun main() {
    val s = "AABABBA"
    val k = 1
    println(characterReplacement(s, k)) // 4
}

func characterReplacement(_ s: String, _ k: Int) -> Int {
    var freq = [Int](repeating: 0, count: 26)
    var left = s.startIndex
    var maxCount = 0
    var maxLen = 0

    for right in s.indices {
        let rightCharIndex = Int(s[right].asciiValue! - Character("A").asciiValue!)
        freq[rightCharIndex] += 1
        maxCount = max(maxCount, freq[rightCharIndex])

        while s.distance(from: left, to: right) + 1 - maxCount > k {
            let leftCharIndex = Int(s[left].asciiValue! - Character("A").asciiValue!)
            freq[leftCharIndex] -= 1
            left = s.index(after: left)
        }

        maxLen = max(maxLen, s.distance(from: left, to: right) + 1)
    }

    return maxLen
}

let s = "AABABBA"
let k = 1
print(characterReplacement(s, k)) // 4

function characterReplacement(s: string, k: number): number {
  const freq: number[] = new Array(26).fill(0);
  let left = 0, maxCount = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    freq[s.charCodeAt(right) - 65]++;
    maxCount = Math.max(maxCount, freq[s.charCodeAt(right) - 65]);

    while ((right - left + 1) - maxCount > k) {
      freq[s.charCodeAt(left) - 65]--;
      left++;
    }

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

  return maxLen;
}

// Example usage
const s = "AABABBA";
const k = 1;
console.log(characterReplacement(s, k)); // 4

Time complexity

Space complexity

O(1)

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.