Leetcode 424. Longest Repeating Character Replacement

Problem

Leetcode 424 - Longest Repeating Character Replacement

Example:

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

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.

Approach

We can use a sliding window technique, and hashMap to count the frequency of element.

We can add the element s[right] every iteration, then update the max frequency.

We can figure out the elements that need swapping with this formula: $swap = (length) - maxF$ if our swap is bigger than k, then we need to move the window.

Visualization of the Approach:

s = 'AABABBA', k = 1
     l
     r
count = {A: 1}
maxF = 1
res = 1

s = 'AABABBA', k = 1
     lr
count = {A: 2}
maxF = 2
res = 2

s = 'AABABBA', k = 1
     l r
count = {A: 2, B: 1}
maxF = 2
Since length - maxF == k, we can ignore
res = 3

s = 'AABABBA', k = 1
     l  r
count = {A: 3, B: 1}
maxF = 3
res = 4

s = 'AABABBA', k = 1
     l   r
count = {A: 3, B: 2}
maxF = 3
Since length - maxF > k, we have to move the window

s = 'AABABBA', k = 1
       l r
count = {A: 1, B: 2}
maxF = 2
Since length - maxF == k, we can ignore
res = 4

s = 'AABABBA', k = 1
       l  r
count = {A: 1, B: 3}
maxF = 3
Since length - maxF == k, we can ignore
res = 4

s = 'AABABBA', k = 1
       l   r
count = {A: 2, B: 3}
maxF = 3
Since length - maxF > k, we have to move the window

s = 'AABABBA', k = 1
         l r
count = {A: 1, B: 2}
maxF = 2
Since length - maxF == k, we can ignore
res = 4

return 4

Here is the Python code for the solution:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        res = 0

        left = 0
        maxF = 0
        for r in range(len(s)):
            count[s[r]] = 1 + count.get(s[r], 0)
            maxF = max(maxF, count[s[r]])

            while (r-left+1) - maxF > k:
                count[s[left]] -= 1
                left += 1
            res = max(res, r - left + 1)
        return res       

Time Complexity and Space Complexity

Time Complexity: $O(n)$ where $n$ represents the length of the string

Space Complexity: $O(m)$ where $m$ represents the total number of unique characters in the string