LeetCode: 424 Longest Repeating Character Replacement

Problem Description:

Given a string s consisting of uppercase letters, you can replace at most k characters with any uppercase letter. Find the length of the longest substring containing the same letter after performing at most k replacements.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace two 'B's with 'A's to get "AAAA".

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace one 'B' with 'A' to get "AABBBBA".

Original Code (Sliding Window Approach):

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}  # Frequency count of characters
        l = 0  # Left pointer
        ans = 0  # Initialize maximum length to 0

        for r in range(len(s)):  # Iterate with right pointer
            count[s[r]] = count.get(s[r], 0) + 1  # Update character frequency

            # Check if the current window size minus max frequency exceeds k
            while (r - l + 1) - max(count.values()) > k:
                count[s[l]] -= 1  # Remove frequency of the left pointer character
                l += 1  # Move left pointer

            ans = max(ans, r - l + 1)  # Update maximum length

        return ans  # Return result

Line-by-Line Explanation and Example Execution:

1. def characterReplacement(self, s: str, k: int) -> int:

   • Defines the main function characterReplacement that takes a string s and an integer k, returning the length of the longest substring.

2. count = {}

   • Initializes a dictionary count to record the frequency of each character.

3. l = 0

   • Initializes the left pointer l, which points to the start of the current window.

4. ans = 0

   • Initializes the maximum length ans to 0.

5. for r in range(len(s)):

   • Iterates through the string with the right pointer r from 0 to the length of the string.

6. count[s[r]] = count.get(s[r], 0) + 1

   • Updates the frequency of the current character s[r], using get to return 0 if the character is not present.

7. while (r - l + 1) - max(count.values()) > k:

   • Checks if the size of the current window minus the maximum frequency exceeds k. If true, it means we need to shrink the window.

8. count[s[l]] -= 1

   • Decreases the frequency of the character at the left pointer.

9. l += 1

   • Moves the left pointer to shrink the window.

10. ans = max(ans, r - l + 1)

    • Updates the maximum length to be the size of the current window.

11. return ans

    • Returns the maximum length.

Example Execution:

Assuming we have the following input:

s = "AABABBA"
k = 1

Execution steps:

1. Initialization:

   • count = {}, l = 0, ans = 0.

2. Iterate through the string:

   • r = 0, s[r] = 'A':
     • count = {'A': 1}, window size 1, max frequency 1, valid window, update ans = 1.
   • r = 1, s[r] = 'A':
     • count = {'A': 2}, window size 2, max frequency 2, valid window, update ans = 2.
   • r = 2, s[r] = 'B':
     • count = {'A': 2, 'B': 1}, window size 3, max frequency 2, valid window, update ans = 3.
   • r = 3, s[r] = 'A':
     • count = {'A': 3, 'B': 1}, window size 4, max frequency 3, valid window, update ans = 4.
   • r = 4, s[r] = 'B':
     • count = {'A': 3, 'B': 2}, window size 5, max frequency 3, invalid window, enter while:
     • Decrease count['A'], update l = 1, now count = {'A': 2, 'B': 2}.
   • r = 5, s[r] = 'B':
     • count = {'A': 2, 'B': 3}, window size 5, max frequency 3, invalid window, enter while:
     • Decrease count['B'], update l = 2, now count = {'A': 2, 'B': 2}.
   • r = 6, s[r] = 'A':
     • count = {'A': 3, 'B': 2}, window size 5, max frequency 3, invalid window, enter while:
     • Decrease count['A'], update l = 3, now count = {'A': 1, 'B': 2}.

3. Final Result:

   • Returns ans = 4.

Time Complexity Analysis:

• Time Complexity: O(n)
  • Where n is the length of the string. Each character is processed at most twice (once by the right pointer and once by the left pointer).

Space Complexity Analysis:

• Space Complexity: O(1)
  • The space used by the frequency dictionary is constant since it only stores the frequency of 26 uppercase letters.

Tips and Warnings:

1. Edge Cases:

   • When the input string is empty, return 0.

2. Character Set Support:

   • The solution assumes the character set consists of uppercase letters; adjustments are needed for other character sets.

3. Understanding Sliding Window:

   • Ensure a clear understanding of the sliding window logic and how to shrink the window when conditions are not met.

Improvement Solutions

The current implementation is efficient and meets the problem requirements. Alternative counting methods can be considered, but there is no significant efficiency improvement.

Summary

• Sliding Window Method: Effectively finds the longest substring after character replacements, with a time complexity of O(n).
• Clear and Understandable: The code is straightforward and easy to comprehend, suitable for handling this type of problem.

Application Tips

1. Choose Appropriate Methods:

   • Select the method best suited to the specific problem requirements to ensure efficiency and readability.

2. Handle Edge Cases:

   • Always consider edge cases in algorithm design to avoid potential errors.

3. Optimize Space Usage:

   • When handling large datasets, consider using space-efficient algorithms.