424. Longest Repeating Character Replacement

How to solve Longest Repeating Character Replacement (LeetCode 424): the approach in brief

The problem

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 English character. You can perform this operation at most k times.

Pattern

Longest Repeating Character Replacement is a Sliding Window problem, in the Variable Size (Condition-Based) subpattern. The pattern covers fixed-size, variable-size, and character frequency matching window techniques

Master variable-size sliding window for condition-based problems like longest substring without repeating characters.

Approach outline

1. Try using a sliding window approach to efficiently examine substrings rather than checking all possible substrings explicitly.
2. Since characters can be replaced up to k times, consider how to maintain a window where at most k characters differ from the most frequent character in that window.
3. Keep track of the count of each character within the current window to help determine if the window is valid based on the allowed replacements.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Longest Repeating Character Replacement has been reported in interviews at Google, Amazon, Wish.