Home → Algorithms → Longest Repeating Character Replacement

Longest Repeating Character Replacement

An interactive visualization of the sliding window algorithm that finds the longest substring with same characters after at most k replacements.

Sliding Window LC 424 Medium

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.

Interactive Visualization

String (uppercase letters):

k (max replacements):

Presets:

Speed:

Window Size

Max Frequency

Replacements Needed

k (Max Allowed)

Max Length

Character Frequency in Window

Start the algorithm to see frequency data

Click Step or Play to start

Code

fun characterReplacement(s: String, k: Int): Int {    val count = mutableMapOf<Char, Int>()    var left = 0    var maxFreq = 0    var maxLen = 0    for (right in s.indices) {        count[s[right]] = (count[s[right]] ?: 0) + 1        maxFreq = maxOf(maxFreq, count[s[right]]!!)        while ((right - left + 1) - maxFreq > k) {            count[s[left]] = count[s[left]]!! - 1            left++        }        maxLen = maxOf(maxLen, right - left + 1)    }    return maxLen}

def characterReplacement(s, k):    count = {}    left = 0    max_freq = 0    max_len = 0        for right in range(len(s)):        count[s[right]] = count.get(s[right], 0) + 1        max_freq = max(max_freq, count[s[right]])                while (right - left + 1) - max_freq > k:            count[s[left]] -= 1            left += 1                max_len = max(max_len, right - left + 1)        return max_len

Key Insight

The sliding window technique maintains a window where the number of characters that need to be replaced (window size minus the most frequent character count) is at most k. By tracking the maximum frequency in the current window, we can efficiently determine when to shrink the window from the left.

Algorithm Steps

Initialize a frequency map, two pointers (left and right), max_freq, and max_len
Expand the window by moving right pointer and update character frequency
Update max_freq to track the highest frequency character in current window
If (window_size - max_freq) > k, shrink window from left until condition is satisfied
Update max_len with the current valid window size
Repeat until right pointer reaches the end of string

Complexity Analysis

Time Complexity	O(n) where n is the length of the string
Space Complexity	O(1) - frequency map contains at most 26 uppercase letters