{x}
blog image

Longest Repeating Character Replacement

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.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

 

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length

Solution Explanation: Longest Repeating Character Replacement

This problem asks to find the length of the longest substring containing the same letter after performing at most k character replacements. The optimal approach is using a sliding window technique combined with a frequency counter (hash map or array).

Algorithm:

  1. Initialization:

    • cnt: A frequency array (or hash map) to store the counts of each character in the current window. We use an array of size 26 since we only have uppercase English letters.
    • l, r: Pointers defining the left and right boundaries of the sliding window. Initially, both are 0.
    • mx: Stores the maximum frequency of any character within the current window.

  2. Sliding Window Iteration:

    • The r pointer iterates through the string s.
    • For each character s[r]:
      • Increment its count in cnt.
      • Update mx to be the maximum frequency seen so far in the window.
      • Window Size Check: If the window size (r - l + 1) minus the maximum frequency (mx) is greater than k, it means we've exceeded the allowed replacements. Therefore:
        • Decrement the count of the character at the left boundary (s[l]) in cnt.
        • Move the left pointer l one position to the right, shrinking the window.

  3. Return Value:

    • After iterating through the entire string, the length of the longest substring is len(s) - l.

Time Complexity: O(n), where n is the length of the string. We iterate through the string once using the sliding window.

Space Complexity: O(1). The frequency array cnt has a constant size of 26 (for uppercase English letters). This is independent of the input string length.

Code Examples:

The provided code snippets demonstrate the algorithm in several programming languages. All versions follow the same core logic:

  • They initialize the frequency array cnt, the pointers l and r, and the maximum frequency mx.
  • They use a for loop to iterate through the string, updating the frequency counts and window boundaries.
  • The condition r - l + 1 - mx > k checks whether the window needs to be shrunk.
  • Finally, they return the length of the longest valid substring.

The only minor differences are in the syntax and data structure usage (e.g., using Counter in Python vs. a standard array in other languages). The underlying algorithmic approach remains consistent.

Example Walkthrough (Python):

Let's consider s = "AABABBA", k = 1.

| r | s[r] | cnt['A'] | cnt['B'] | mx | r - l + 1 | r - l + 1 - mx | Condition | l | Resulting Substring | |---|---|---|---|---|---|---|---|---|---| | 0 | A | 1 | 0 | 1 | 1 | 0 | False | 0 | A | | 1 | A | 2 | 0 | 2 | 2 | 0 | False | 0 | AA | | 2 | B | 2 | 1 | 2 | 3 | 1 | False | 0 | AAB | | 3 | A | 3 | 1 | 3 | 4 | 1 | False | 0 | AABA | | 4 | B | 3 | 2 | 3 | 5 | 2 | True | 1 | ABA | | 5 | B | 3 | 3 | 3 | 5 | 2 | True | 2 | BAB | | 6 | A | 4 | 3 | 4 | 7 | 3 | True | 3 | ABBA |

The loop continues until r reaches the end. The longest substring length is len(s) - l = 7 - 3 = 4. The final valid substring could be "BBBB" (achieved by replacing one 'A').

This detailed explanation, along with the diverse code examples, should provide a complete understanding of the solution to the Longest Repeating Character Replacement problem.