Longest Repeating Character Replacement Algorithm

The Longest Repeating Character Replacement problem asks us to determine the maximum length of a substring where we can make all characters identical by replacing at most k characters. This classic sliding window problem demonstrates efficient string manipulation techniques.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input string contain only uppercase English letters, or could it have lowercase letters too?
2. What is the expected time complexity constraint? Should we aim for O(n) or can we accept O(n²)?
3. Are we allowed to modify the input string in-place, or should we return a new result?
4. What is the maximum length of the input string we need to handle?
5. Should we return just the length of the longest substring or also provide the actual substring?

Restated problem in my own words: Given a string of uppercase English letters and an integer k, we want to find the length of the longest substring that can be made entirely of one character by replacing at most k characters in that substring with any other uppercase letter.

Input/output specification:

• Input: A string s of length n (1 ≤ n ≤ 10⁵) containing only uppercase English letters, and integer k (0 ≤ k ≤ n)
• Output: An integer representing the maximum length of a substring that can be made uniform by replacing at most k characters

Constraints:

• String contains only uppercase English letters (A-Z)
• k is non-negative and at most the length of the string
• We can make at most k replacements

Assumptions I'm making:

1. The string is not null or empty (minimum length 1)
2. We're looking for the maximum length, not the actual substring itself
3. The input string can be modified during processing (we can use a mutable data structure)
4. We're allowed to make at most k replacements in any chosen substring

Data shape and hidden structure: The problem exhibits a sliding window pattern where we're looking for the optimal window size that satisfies our constraint. The "repeating character" aspect suggests we're trying to maximize a window where the most frequent character in that window appears frequently enough that we can make all characters in the window match it by replacing at most k characters. The key insight is that we don't need to track the actual substring, just its length.

The problem has a hidden structure where we're essentially looking for the maximum window size such that (window_size - max_frequency_in_window) ≤ k. This is because we can only make at most k replacements to make all characters in the window the same.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern here is sliding window technique with a frequency-based optimization.

Why this problem fits that pattern

The problem asks for the length of the longest substring where we can make all characters the same by replacing at most k characters. This is a classic sliding window problem where:

• We want to find the maximum length of a valid substring
• A "valid" substring is one where we need at most k replacements to make all characters identical
• The constraint that we can replace at most k characters creates a bounded window condition

Core insight needed to solve it

The key insight is that for any valid window, we only need to keep track of the maximum frequency character in that window. If we have a window where the most frequent character appears maxFreq times, and the window size is windowSize, then we need windowSize - maxFreq replacements to make all characters in that window the same. As long as this number is ≤ k, the window is valid.

The pattern is that we can maintain a sliding window where:

1. We expand the right boundary until we have a valid window
2. When we exceed the limit (windowSize - maxFreq > k), we shrink from the left
3. We track the maximum valid window size throughout the process

This is a variable-size sliding window where the window size can grow and shrink dynamically based on the constraint.

Wording that signals this pattern

• "Longest substring" → suggests we're looking for an optimal window size
• "Replace at most k characters" → creates a constraint on how many elements can be different from the most frequent character in our window
• "Make all characters the same" → suggests we're optimizing around a target character that appears most frequently in our window

3. Approach Evolution

My first instinct is to use a sliding window approach because this problem asks for the longest substring with at most k replacements, which naturally fits a window-based pattern. However, I need to think carefully about how to track the replacements efficiently.

Let me think about a brute force approach first: I could check every possible substring and for each one, count character frequencies and determine if it can be made uniform with at most k replacements. But that would be O(n³) - O(n²) substrings, and for each substring we'd need O(n) to count frequencies. That's definitely not optimal.

I can optimize this by using a sliding window with two pointers. The key insight is that for any valid window, we only need to know the maximum frequency of a character in that window. If the window size minus this max frequency is ≤ k, then we can make all characters in that window the same with at most k replacements.

Let me trace through this more carefully: if I have a window of size windowSize and the most frequent character appears maxFreq times, then I need to replace windowSize - maxFreq characters. If this number is ≤ k, the window is valid.

The optimization I'm using here is that instead of recalculating character frequencies from scratch for every window position, I maintain a running count and update it incrementally. This gives me O(n) time complexity.

The key invariant I must maintain is that at any point in the sliding window, the current window size minus the maximum frequency character count should be ≤ k. This ensures that we can make all characters in the window identical with at most k replacements.

My approach is to use two pointers (left and right) to maintain a sliding window, keep track of character frequencies in the current window, and expand the right pointer while maintaining validity. When validity is broken, I shrink from the left until it's restored.

The core insight is that we never need to shrink the window size when we find a better answer - we only expand it. This is because if we find a valid window of size S, and we later find a valid window of size S+1, that larger window is always better than any previous window of size S.

This approach works because we're looking for the maximum possible window size that satisfies our constraint, and we can greedily expand the window as long as it remains valid.

4. Data Structure Choice

For this problem, I'll use a sliding window approach with a frequency map as my primary data structures.

Primary Data Structures

1. HashMap<Character, Integer> - Used to maintain the frequency count of characters in the current window

   • Why needed: We need to quickly look up and update character frequencies as we expand/contract the window
   • Time impact: O(1) average for get/put operations
   • Space impact: O(k) where k is the size of the character set (at most 26 for uppercase English letters)

2. Two pointers (int left, int right) - Used to maintain the sliding window bounds

   • Why needed: To efficiently track the current window of characters being considered
   • Time impact: O(1) for pointer operations
   • Space impact: O(1) - just two integers

3. int maxFreq - Track the maximum frequency of any character in current window

   • Why needed: To avoid recalculating max frequency on every window expansion, which would be inefficient
   • Time impact: O(1) for updates
   • Space impact: O(1)

Why This Choice Is Optimal

The HashMap provides the perfect balance for this sliding window problem:

• It allows us to efficiently maintain character frequencies without needing to recompute them
• It handles the dynamic nature of the window size gracefully
• It's more space-efficient than using a fixed-size array for character frequencies (which would require 256+ entries for ASCII)
• The two-pointer approach naturally fits with the sliding window paradigm

The key insight is that we don't need to track all character frequencies constantly - we only care about the maximum frequency in our current window, which allows us to make optimal decisions about when to expand or contract the window.

Helper Structure

I'm not using any additional helper structures beyond what's necessary for the sliding window approach. The solution maintains a clean, minimal data structure footprint while providing optimal performance characteristics for this specific problem pattern.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works.

Example: s = "AABABBA", k = 1

Step-by-step execution:

1. Initialize variables:

   • left = 0, maxLength = 0
   • charCount = [A:0, B:0] (HashMap tracking character frequencies)
   • maxCharCount = 0 (maximum frequency of any character in current window)

2. Expand window with right pointer:

   • right = 0: char = 'A'
     • Increment charCount['A'] to 1
     • Update maxCharCount = max(0, 1) = 1
     • Window size = 1, maxCharCount = 1, so 1 - 1 = 0 ≤ k = 1 ✓
     • Update maxLength = max(0, 1) = 1

3. Continue expanding:

   • right = 1: char = 'A'
     • charCount['A'] becomes 2
     • maxCharCount = max(1, 2) = 2
     • Window size = 2, maxCharCount = 2, so 2 - 2 = 0 ≤ k = 1 ✓
     • Update maxLength = max(1, 2) = 2

4. Continue expanding:

   • right = 2: char = 'B'
     • charCount['B'] becomes 1
     • maxCharCount = max(2, 1) = 2 (unchanged)
     • Window size = 3, maxCharCount = 2, so 3 - 2 = 1 ≤ k = 1 ✓
     • Update maxLength = max(2, 3) = 3

5. Continue expanding:

   • right = 3: char = 'A'
     • charCount['A'] becomes 3
     • maxCharCount = max(2, 3) = 3
     • Window size = 4, maxCharCount = 3, so 4 - 3 = 1 ≤ k = 1 ✓
     • Update maxLength = max(3, 4) = 4

6. Continue expanding:

   • right = 4: char = 'B'
     • charCount['B'] becomes 2
     • maxCharCount = max(3, 2) = 3 (unchanged)
     • Window size = 5, maxCharCount = 3, so 5 - 3 = 2 > k = 1 ✗
     • Shrink window: Move left pointer right and decrement count of s[left]
     • charCount['A'] becomes 2, left = 1

7. Continue expanding:

   • right = 5: char = 'B'
     • charCount['B'] becomes 3
     • maxCharCount = max(3, 3) = 3
     • Window size = 5, maxCharCount = 3, so 5 - 3 = 2 > k = 1 ✗
     • Shrink window: Move left pointer right and decrement count of s[left]
     • charCount['A'] becomes 1, left = 2

8. Continue expanding:

   • right = 6: char = 'A'
     • charCount['A'] becomes 2
     • maxCharCount = max(3, 2) = 3
     • Window size = 5, maxCharCount = 3, so 5 - 3 = 2 > k = 1 ✗
     • Shrink window: Move left pointer right and decrement count of s[left]
     • charCount['B'] becomes 2, left = 3

9. Final state:

   • right = 7: char = 'A'
     • Window size = 5, maxCharCount = 3, so 5 - 3 = 2 > k = 1 ✗
     • Shrink window: Move left pointer right and decrement count of s[left]
     • charCount['A'] becomes 1, left = 4

Result: The maximum valid window size found was 4, so return 4.

Key insight: The algorithm maintains a sliding window where the number of characters that need to be replaced (window size - max frequency) is ≤ k. It always keeps track of the maximum frequency character in the current window, which allows us to make optimal decisions without having to check all possible replacement strategies.

Edge case handling:

• When window size = 1, we can always make a valid replacement since 1 - 1 = 0 ≤ k
• When we detect an invalid window, we shrink it from the left until validity is restored
• The algorithm correctly handles cases where all characters are the same or where we can make optimal replacements

6. Java Solution

public class Solution {
    public int characterReplacement(String s, int k) {
        // Edge case: empty string
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        // Sliding window approach
        int left = 0;
        int maxLength = 0;
        int maxFreq = 0;
        int[] charCount = new int[26]; // Assuming only uppercase English letters
        
        // Expand window by moving right pointer
        for (int right = 0; right < s.length(); right++) {
            // Update count of current character
            char rightChar = s.charAt(right);
            charCount[rightChar - 'A']++;
            
            // Update maximum frequency in current window
            maxFreq = Math.max(maxFreq, charCount[rightChar - 'A']);
            
            // Shrink window if we need to make more than k replacements
            // Window size minus max frequency gives us the number of characters 
            // that need to be replaced
            while ((right - left + 1) - maxFreq > k) {
                char leftChar = s.charAt(left);
                charCount[leftChar - 'A']--;
                left++;
            }
            
            // Update maximum length of valid window
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

This solution uses a sliding window technique with two pointers to find the longest substring where we can make all characters the same by replacing at most k characters. The key insight is that for any valid window, we only need to track the character with maximum frequency to determine how many replacements are needed.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers that traverse the input string exactly once. The outer while loop runs for each character in the string, and the inner while loop (which adjusts the left pointer) can only execute at most n times across all iterations. Since we're processing each character at most twice (once by the right pointer, once by the left pointer), the total time complexity is linear.

Space Complexity: O(1)

The space usage is constant because we only maintain a fixed-size array of size 26 (for uppercase English letters) to store character frequencies. The additional variables used for tracking window state (left, right, maxFreq, maxLength) are all scalar values that don't scale with input size. The algorithm does not use any data structures whose space grows with the input.

Why These Bounds Are Correct

The linear time complexity follows directly from the sliding window technique where each element is visited at most twice. The constant space complexity stems from the fact that we're only tracking character frequencies for a fixed alphabet size (26 uppercase English letters), which is independent of input size.

This solution is optimal because:

1. We must examine each character at least once to determine the longest valid substring
2. The sliding window approach is the most efficient way to solve this type of maximum/minimum substring problem with constraints
3. No better algorithm exists for this specific constraint (at most k replacements allowed)

The solution achieves the theoretical lower bound of O(n) time and O(1) space for this problem.

8. Edge Cases & Pitkins

Edge cases that require careful handling:

Empty input and single character:

• Empty string returns 0 (no replacements possible)
• Single character string returns 1 (can replace to itself)
• These cases should be handled explicitly to avoid index errors

All same characters:

• Input like "AAAA" with k=2 should return 4 (no replacements needed)
• The algorithm must correctly handle when no replacements are necessary

All different characters:

• Input like "ABCD" with k=2 should return 3 (replace 2 of the 4 chars to match one character)
• Need to ensure sliding window properly shrinks when no valid window exists

k=0 edge case:

• When k=0, we can only extend existing same-character sequences
• Must handle this special case correctly in window management

Boundary conditions:

• Window size of 1, k=0 should return 1
• Window size equals string length with k≥0 should return string length
• When window shrinks, ensure we don't go below minimum valid size

Common implementation pitfalls:

1. Incorrect window shrinking logic:

   • Not properly tracking the maximum frequency character in current window
   • Shrinking window when it should remain or expand instead

2. Off-by-one errors in window bounds:

   • Using <= vs < in loop conditions
   • Incorrectly updating left pointer position

3. Frequency tracking errors:

   • Not decrementing character counts when removing from window
   • Using wrong character index in frequency array

4. Not handling character frequency properly:

   • Assuming all characters are ASCII letters (should handle any valid input)
   • Not resetting character counts properly during window shifts

5. Integer overflow in large inputs:

   • Though not a practical concern for this problem, should be aware of potential issues with very large inputs

The solution must maintain proper invariants: window size never decreases below valid range, character frequency counts are always accurate, and the maximum frequency in current window is correctly tracked.

9. Alternative Approaches

There are several alternative approaches to solving the longest repeating character replacement problem, each with different trade-offs:

Brute Force Approach: Check every possible substring and for each, determine the minimum replacements needed to make all characters the same. For each substring of length k, we'd count character frequencies and find the maximum frequency character, then compute k - maxFreq as replacements needed. This approach has O(n³) time complexity due to checking all substrings and counting frequencies for each.

Sliding Window with Frequency Map: Instead of tracking the maximum frequency character explicitly, we can maintain a frequency map and always track the maximum frequency as we expand the window. When windowSize - maxFreq > k, we shrink the window from the left. This is essentially the same as our chosen approach but with a slightly different implementation pattern.

Two Pointers with Character Tracking: Use two pointers to maintain a sliding window, but instead of tracking character frequencies, we could track the count of each character in the current window and adjust our window size based on how many characters need to be changed. This approach is functionally equivalent but requires more careful boundary condition handling.

Binary Search on Answer: Since we're looking for the maximum length, we could binary search on the answer. For each potential window size, check if there exists a valid window of that size using our sliding window technique. This would result in O(n log n) time complexity but is more complex to implement.

The chosen sliding window approach with frequency tracking is preferred because it's simpler to understand, more intuitive to implement correctly, and has optimal O(n) time complexity. The alternatives either introduce unnecessary complexity or increase time complexity without providing significant benefits for this specific problem structure.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem description
        // Input: s = "ABAB", k = 2
        // Expected: 4 (replace both A's with B's or vice versa)
        System.out.println("Test 1: " + new Solution().characterReplacement("ABAB", 2)); // Expected: 4
        
        // Test case 2: Single character input
        // Input: s = "A", k = 0
        // Expected: 1 (no replacements allowed)
        System.out.println("Test 2: " - new Solution().characterReplacement("A", 0)); // Expected: 1
        
        // Test case 3: All same characters
        // Input: s = "AAAA", k = 2
        // Expected: 4 (no replacements needed)
        System.out.println("Test 3: " + new Solution().characterReplacement("AAAA", 2)); // Expected: 4
        
        // Test case 4: Mixed characters with limited replacements
        // Input: s = "AABABBA", k = 1
        // Expected: 4 (replace one B with A to get "AAABA" or similar)
        System.out.println("Test 4: " + new Solution().characterReplacement("AABABBA", 1)); // Expected: 4
        
        // Test case 5: Edge case - zero k
        // Input: s = "AABA", k = 0
        // Expected: 2 (no replacements, longest repeating substring)
        System.out.println("Test 5: " + new Solution().characterReplacement("AABA", 0)); // Expected: 2
        
        // Test case 6: Large k value
        // Input: s = "ABCDE", k = 10
        // Expected: 5 (can replace all to make one character)
        System.out.println("Test 6: " + new Solution().characterReplacement("ABCDE", 10)); // Expected: 5
        
        // Test case 7: Empty string
        // Input: s = "", k = 1
        // Expected: 0 (empty string)
        System.out.println("Test 7: " + new Solution().characterReplacement("", 1)); // Expected: 0
    }
}

Sample Test Cases:

Basic Example:

• Input: s = "ABAB", k = 2
• Expected Output: 4
• Explanation: Replace both A's or B's to get a repeating character string of length 4

Single Character:

• Input: s = "A", k = 0
• Expected Output: 1
• Explanation: No replacements allowed, so maximum length is 1

All Same Characters:

• Input: s = "AAAA", k = 2
• Expected Output: 4
• Explanation: No replacements needed, entire string is valid

Mixed Characters:

• Input: s = "AABABBA", k = 1
• Expected Output: 4
• Explanation: Replace one character to make longest repeating substring

Edge Case - Zero K:

• Input: s = "AABA", k = 0
• Expected Output: 2
• Explanation: No replacements allowed, longest repeating substring is 2

Large K:

• Input: s = "ABCDE", k = 10
• Expected Output: 5
• Explanation: With enough replacements, we can make any character appear 5 times

Empty String:

• Input: s = "", k = 1
• Expected Output: 0
• Explanation: Empty string has zero length regardless of k value

11. Final Summary

The core insight is to use a sliding window approach to find the longest substring where we can make all characters the same by replacing at most k characters. By maintaining a window that satisfies the constraint (window size - max frequency ≤ k), we can efficiently track the optimal solution using a single pass through the string.

This solution works because it leverages the key observation that for any valid window, the maximum length substring will have a window size equal to the current window size minus the count of the most frequent character in that window. The algorithm is optimal with O(n) time and O(1) space complexity, making it ideal for large inputs.

The efficiency comes from avoiding redundant checks by maintaining a valid sliding window and using the frequency map to track character counts without recalculating from scratch at each step.