Longest Repeating Character Replacement – 424. LeetCode

The Longest Repeating Character Replacement problem asks you to find the length of the longest substring in a given string that can be made up of only one repeating character after replacing at most k characters. For example, in the string “AABABBA” with k = 1, the longest substring is “AABABBA” (length 4) because we can replace one “B” to form “AAAA” or “BBBB”.

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 letter

This problem is about balancing modifications and maximizing the length of a valid substring.

Brute Force Approach

We use nested loops to check every possible substring and count how many characters need to be replaced to make all characters in the substring the same. If the replacements required are less than or equal to k, update the maximum substring length.

    public static int characterReplacement(String s, int k) {
        int maxLength = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) { // Outer loop to fix starting index
            for (int j = i; j < n; j++) { // Inner loop to fix ending index
                int[] freq = new int[26];
                for (int p = i; p <= j; p++) { // Count character frequencies
                    freq[s.charAt(p) - 'A']++;
                }
                int maxFreq = 0;
                for (int f : freq) { // Find the most frequent character
                    maxFreq = Math.max(maxFreq, f);
                }
                int length = j - i + 1; // Substring length
                if (length - maxFreq <= k) { // Check if replacement is valid
                    maxLength = Math.max(maxLength, length);
                }
            }
        }

        return maxLength;
    }

Optimal Approach: Sliding Window with Frequency Count

To optimize, use the Sliding Window pattern with a frequency array to track character counts. Instead of checking all substrings, expand and shrink a window dynamically while ensuring the window remains valid.

Algorithmic and Data Structure Pattern

• Pattern: Sliding Window

• Use a window (defined by two pointers) to represent the current substring.

• Expand the window by moving the right pointer.

• Shrink the window by moving the left pointer if replacements exceed k.

• Data Structure: Frequency Array

• A fixed-size array (int[26]) tracks character frequencies in the window.

Why This Approach Works

• Sliding Window ensures we process the string in linear time by maintaining a valid substring and adjusting only as needed.

• Frequency Array efficiently tracks the number of replacements required.

Steps of the Algorithm

1. Initialize:

• left pointer at 0.

• maxFreq to track the highest frequency of a character in the window.

2. Expand the window by moving the right pointer.

3. Calculate replacements needed using windowLength – maxFreq.

4. If replacements exceed k, shrink the window by moving the left pointer.

5. Keep track of the maximum valid window length.

    public static int characterReplacement(String s, int k) {
        int[] freq = new int[26]; // Frequency array for characters
        int left = 0, maxFreq = 0, maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            // Update frequency of current character
            freq[s.charAt(right) - 'A']++;
            // Update max frequency in the window
            maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'A']);

            // Check if replacements exceed k
            if ((right - left + 1) - maxFreq > k) {
                // Shrink window
                freq[s.charAt(left) - 'A']--;
                left++;
            }

            // Update max length of valid substring
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

Explanation of Code

1. Create Char Frequency Array

int[] freq = new int[26]; // Frequency array for characters

• Create an array with elements for 26 letters. Each element will track how many characters we have in our current candy lineup.

2. Assign state

int left = 0, maxFreq = 0, maxLength = 0;

• Set left to 0 to initialize pointer at the start
• Keep track of highest frequency letter with maxFreq

2. Add To Character Frequency

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

• Move the right frequency along
• Increase the count of the candy that was just added.
• Update the maxFreq to ensure we know the most common candy type in the lineup.

3. Check if the Lineup Overloaded

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

• Calculate replacements required (windowLength – maxFreq) and check if it exceeds k.
• If replacements exceed k, shrink the window by moving left and updating the frequency.
• Update the maximum valid window length

Why This Algorithm is Better

• Efficiency: Time complexity is O(n) because each character is processed at most twice (once added, once removed).

• Space Complexity: Only O(26) for the frequency array.

• Sliding Window Benefit: Avoids recomputing frequencies for every substring, unlike the brute force approach (O(n^3)).

This optimized approach is clean, concise, and leverages the sliding window pattern for efficiency.