Longest Repeating Character Replacement

Problem Statement

You are given:

A string s consisting of uppercase English letters.
An integer k representing the maximum number of changes allowed.

You can perform at most k operations. In each operation, you can change any character of the string to any other uppercase English letter.

Goal: Find the length of the longest substring that can be transformed into a string with all identical characters after performing at most k changes.

Examples

Example 1

Input: s = "ABBA", k = 2
Output: 4

Explanation: Change both 'A' to 'B' → "BBBB". Max substring length = 4

Example 2

Input: s = "ADBD", k = 1
Output: 3

Explanation: Change 'B' to 'D' → "ADDD". Max substring length = 3

Understanding the Problem

We want the longest substring where most characters are the same, and at most k characters need to be replaced to make all characters identical.

Key Observation:

In a substring, let maxCount be the count of the most frequent character.
The number of changes required is:

changes_needed = window_size - maxCount

If changes_needed <= k, the substring is valid.

Approach: Sliding Window

Use two pointers: left and right to define a window.
Maintain a frequency array of letters in the current window.
Track maxCount — the maximum frequency of any letter in the window.
Expand the window to the right. If the window becomes invalid (window_size - maxCount > k), shrink it from the left.
Track the maximum window size as you slide.

Implementation in C#

public class Solution
{
    public int longestSubstr(string s, int k)
    {
        int[] count = new int[26]; // Frequency array for 'A'-'Z'
        int maxCount = 0;           // Max frequency in current window
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.Length; right++)
        {
            count[s[right] - 'A']++;
            maxCount = Math.Max(maxCount, count[s[right] - 'A']);

            // If more than k changes needed, shrink window
            while ((right - left + 1) - maxCount > k)
            {
                count[s[left] - 'A']--;
                left++;
            }

            maxLength = Math.Max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

Step-by-Step Example: "ABBA", k = 2

Window: A
Window Size: 1
Max Count: 1
Changes Needed: 0
Valid: Yes
Max Length: 1
Window: AB
Window Size: 2
Max Count: 1
Changes Needed: 1
Valid: Yes
Max Length: 2
Window: ABB
Window Size: 3
Max Count: 2
Changes Needed: 1
Valid: Yes
Max Length: 3
Window: ABBA
Window Size: 4
Max Count: 2
Changes Needed: 2
Valid: Yes
Max Length: 4

Output: 4

Explanation: Change both 'A' to 'B' → "BBBB".

Complexity Analysis

Time Complexity: O(n) — Each character is processed at most twice (entering and leaving the window).
Space Complexity: O(1) — Frequency array of size 26.

Conclusion

The sliding window technique combined with a frequency array allows us to efficiently find the longest substring that can be transformed into all identical characters.

This method works even for large strings up to 10^5 characters.