Longest Repeating Character Replacement

NeetCode: Longest Repeating Character Replacement · LeetCode: 424. Longest Repeating Character Replacement · Difficulty: Medium

Given an uppercase string s and an integer k, you may replace up to k characters with any other uppercase letter. Return the length of the longest substring that can be made of a single repeated letter.

Example

Text

Input:  s = "XYYX",    k = 2    Output: 4
Input:  s = "AAABABB", k = 1    Output: 5

Brute force: try every substring

char arithmetic gives the letter index: s.charAt(i) - 'A' is an int from 0 to 25. char arithmetic gives the letter index: s.charAt(i) - 'A' is an int from 0 to 25. char arithmetic gives the letter index: s.charAt(i) - 'A' is an int from 0 to 25. A substring of length len can be fixed with k replacements if len - (count of its most common letter) <= k.

Java

class Solution {
    public int characterReplacement(String s, int k) {
        int best = 0;
        for (int start = 0; start < s.length(); start++) {
            int[] counts = new int[26];
            int maxCount = 0;
            for (int end = start; end < s.length(); end++) {
                int idx = s.charAt(end) - 'A';
                counts[idx]++;
                maxCount = Math.max(maxCount, counts[idx]);
                int len = end - start + 1;
                if (len - maxCount <= k) {
                    best = Math.max(best, len);
                }
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.characterReplacement("XYYX", 2));
        System.out.println(s.characterReplacement("AAABABB", 1));
    }
}

Output

4
5

Time: O(n²). Space: O(1).

Optimal: sliding window with the max frequency

Grow the window by moving right. If the window needs more than k replacements (length - maxCount > k), slide it by moving left one step. maxCount is never lowered when the window shrinks. The answer can only grow when maxCount reaches a new high, so a stale, too-large value cannot produce a wrongly long window.

Java

class Solution {
    public int characterReplacement(String s, int k) {
        int[] counts = new int[26];
        int left = 0;
        int maxCount = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            int idx = s.charAt(right) - 'A';
            counts[idx]++;
            maxCount = Math.max(maxCount, counts[idx]);
            while (right + 1 - left - maxCount > k) {
                counts[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right + 1 - left);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.characterReplacement("XYYX", 2));
        System.out.println(s.characterReplacement("AAABABB", 1));
    }
}

Output

4
5

Time: O(n). Space: O(1).