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.