424.Longest_Repeating_Character_Replacement(Medium).md

424. Longest Repeating Character Replacement (Medium)

Date and Time: Jul 10, 2024, 17:46 (EST)

Link: https://leetcode.com/problems/longest-repeating-character-replacement/

Question:

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 <= 10^5

• s consists of only uppercase English letters.

• 0 <= k <= s.length

KeyPoints:

Using sliding window technique, we have l, r pointers to keep track of a range of elements in s, we use hashmap to keep track of the counts of each element and we update the hashmap when we have enough k to subtract for the most counts element or we move the l pointer when we don't have enough k for (r - l + 1) - k.

(r - l + 1) - k is to check for current range of elements, if the most repeated element can replace other elements with k times and make it to be the most repeated element, if not, we need to use while loop to increment l to fix the size of current range have enough k times of operations for that element.

Refined Solution:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        res = 0
        hashmap = {}
        l = 0
        for r in range(len(s)):
            hashmap[s[r]] = 1 + hashmap.get(s[r], 0)
            while (r - l + 1) - max(hashmap.values()) > k:
                hashmap[s[l]] -= 1
                l += 1
            res = max((r - l + 1), res)
        return res

My Solution:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # Use Hashmap to record a range of each element counts
        # If len(range) - most_frequent_counts > k, l += 1
        # Otherwise, r += 1, res = max(res, r - l + 1)
        res = 0
        hashmap = {}
        l, r = 0, 0
        while r < len(s):
            if s[r] in hashmap:
                hashmap[s[r]] += 1
            else:
                hashmap[s[r]] = 1
            while (r - l + 1) - max(hashmap.values()) > k:
                hashmap[s[l]] -= 1
                l += 1
            res = max((r - l + 1), res)
            r += 1
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$