Longest Repeating Character Replacement – 424. LeetCode

The Longest Repeating Character Replacement problem asks us to find the length of the longest substring in a string s that can be transformed into a substring with all identical characters by replacing at most k characters. For example, in the string “AABABBA” with k = 1, the longest substring is “AABBA”, achieved by replacing one “B”.

This is a classic sliding window problem, where the goal is to efficiently find a subarray (or substring) that satisfies a given condition.

Brute Force Approach

The brute force approach involves checking every possible substring, calculating how many characters need to be replaced, and verifying if it meets the condition.

public class LongestRepeatingCharacterReplacement {
    public int characterReplacement(String s, int k) {
        int maxLength = 0;

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                int[] count = new int[26];
                int maxFreq = 0;
                for (int x = i; x <= j; x++) {
                    count[s.charAt(x) - 'A']++;
                    maxFreq = Math.max(maxFreq, count[s.charAt(x) - 'A']);
                }
                int charsToReplace = (j - i + 1) - maxFreq;
                if (charsToReplace <= k) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }

        return maxLength;
    }
}

Step 1: Iterate Over All Possible Start Indices

for (int i = 0; i < s.length(); i++) {

• Iterates over every possible starting index.

Step 2: Iterate Over All Possible End Indices

for (int j = i; j < s.length(); j++) {

• Iterates over all possible ending indices j for the current starting index i.

Step 3: Initialize a Frequency Map and Calculate Frequencies

int[] count = new int[26];
int maxFreq = 0;
for (int x = i; x <= j; x++) {
    count[s.charAt(x) - 'A']++;
    maxFreq = Math.max(maxFreq, count[s.charAt(x) - 'A']);
}

• Initialize an array count of size 26 to track the frequency of each character in the substring.
• Updates the frequency for the current character at position x.
• Updates maxFreq to store the frequenct of the most common character in the substring.

Step 4: Calculate Characters To Replace

int charsToReplace = (j - i + 1) - maxFreq;

• Calculates the number of chracters in the substring that need to be replaced to make the substring uniform.
• j – i + 1 is the length of the substring.
• Subtracting maxFreq gives the number of non-matching characters.

Step 5: Check Validity and Update Max Length

if (charsToReplace <= k) {
    maxLength = Math.max(maxLength, j - i + 1);
}

• Checks if the substring can be transform with at most k replacements.

Step 6: Return

return maxLength;

• Return the length of the longest valid substring found.

Optimized Approach

The optimized solution uses a sliding window approach with a frequency map to dynamically maintain the state of the current substring and determine the result in linear time.

Why a Frequency Map Fits the Problem

• The frequency map (an array of size 26 for English alphabets) provides O(1) operations for updating and querying frequencies. This efficiency is critical when processing large strings.

• To determine the number of replacements needed, we only need the most frequent character in the current window. The frequency map makes this easy by storing counts for all characters in the window.

• Without a frequency map, we would need to recompute character frequencies for every substring, leading to O(N^2) or worse complexity. The map ensures the character frequencies are updated incrementally, optimizing the process.

Why Sliding Window Fits The Problem

• Instead of repeatedly recalculating characters counts for all substrings, the sliding window dynamically adjusts the range while maintaining state.

public class LongestRepeatingCharacterReplacement {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26]; // Frequency map for characters
        int start = 0, maxFreq = 0, maxLength = 0;

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

            // Check if the window is valid
            int windowLength = end - start + 1;
            if (windowLength - maxFreq > k) {
                // Shrink the window from the left
                count[s.charAt(start) - 'A']--;
                start++;
            }

            // Update the maximum length of a valid window
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }
}

Line-By-Line Explanation

Step 1: Initialization

int[] count = new int[26]; // Frequency map for characters
int start = 0, maxFreq = 0, maxLength = 0;

• count: A frequency map to track the count of each character in the current sliding window.
• start: The start index of sliding window.
• maxFreq: Tracks the maximum frequency of any character in the current window.
• maxLength: Stores the length of the longest valid substring found so far.

Step 2: Expand the Window

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

• Iterates through the string with the end pointer.
• Updates the frequency of the character at end in the frequency map (count).
• Updates maxFreq with the frequency of the most frequent character in the window.

Step 3: Calculate Window Length

int windowLength = end - start + 1;

• Calculates the current window size.
• The window size is the distance between the end and start pointers.
• The algorithm uses the window length to determine the number of characters that need replacement to make the window valid.

Step 4: Validate The Window

if (windowLength - maxFreq > k) {
    count[s.charAt(start) - 'A']--;
    start++;
}

• Checks if the number of replacements required exceeds k.
• If replacement exceed k, shrinks the window by moving the start pointer and updating the frequency map for the removed character.

Step 5: Update the Result

maxLength = Math.max(maxLength, end - start + 1);

• Updates maxLength with the size of the current valid window if it’s the longest found so far.

Step 6: Return the Result

return maxLength;

• Clean and explicit return statement directly provides the result.

Why This Code Works

1. Optimal Sliding Window:

• Efficiently uses the sliding window technique, processing each character at most twice.

2. Dynamic Updates:

• Dynamically adjusts the window size, avoiding unnecessary recomputation.

3. Space Efficient:

• Uses a fixed-size array for character frequency, ensuring O(1) space complexity.

4. Clear and Readable:

• Well-structured with clear variable names and concise logic.