_424. Longest Repeating Character Replacement.md

424. Longest Repeating Character Replacement

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 11, 2024

Last updated : July 11, 2024

---

Related Topics : Hash Table, String, Sliding Window

Acceptance Rate : 54.453 %

---

Version 5 (Optimal)

The final optimization that had to be made was not updating the max frequency
downwards at any given moment. Since we're only looking at the context of our
window, the maximal window will require the most repeated characters, since all
others must be changed to match them. Therefore, if the max frequency goes down,
we know for certain that that window won't be valid, so we should just 
shift over an index for both the left and right pointers.

This brought the runtime down to around 75ms, in line with all the 
submitted optimal solutions and perfectly within the bell curve.

Version 4

Here, I changed out the way I'd calculate the total number of 
non-max frequency characters to a mathematical approach. I had overlooked 
it in my haste initially, but the number of characters that would have to be 
changed was simply the length - the frequency of the most frequent character.

The effect was essentially unnoticable however based on how LeetCode 
runs their tests and the time remained similar to Version 3.

Version 3

Compared to Version 2, the improvment here was minimal. I adjusted the 
tracking variable for the longest window to start at length k, since we'd 
at minimum find a case where every letter is unique, thus giving us a result
of k+1 length.

This reduced the time down to around 180ms and the 11% region.

Version 2

In this version, I made the slight adjustment to only check windows
that were larger than the previous window size. This was a step
in the right direction, and was based on a similar idea as the optimal 
solution as it turns out.

This small adjustment resulted in a drop to 320ms per run.

Version 1

This was my first attempt at the question which passed without 
any TLE issues first try in under 9 minutes. However, it was on 
the brink of a TLE. On average, the runtime was measured at the 
bottom 5%, taking 520ms approx. The idea was correct, 
but it did need some modifications.

---

Solutions

• m424 v1 O(n) but inefficient.py
• m424 v2 40 percent improvement.py
• m424 v3 Additional bit of performance.py
• m424 v4 Removed O(k) Summations for Math.py
• m424 v5 Optimal.py

Python

m424 v1 O(n) but inefficient.py

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = Counter(s[0])

        longest = 0
        left, right = 0, 0
        while right < len(s) :
            maxxChar = max(cnt, key=lambda x: cnt[x])
            sumOthers = sum([cnt[x] for x in cnt if x != maxxChar])

            if sumOthers > k :
                cnt[s[left]] -= 1
                left += 1

            else :
                longest = max(longest, sumOthers + cnt[maxxChar])
                right += 1
                if right < len(s) :
                    cnt[s[right]] += 1

        return longest

m424 v2 40 percent improvement.py

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = Counter(s[0])

        longest = 0
        left, right = 0, 0
        while right < len(s) :
            if right - left + 1 <= longest :
                right += 1
                if right < len(s) :
                    cnt[s[right]] += 1
                continue

            maxxChar = max(cnt, key=lambda x: cnt[x])
            sumOthers = sum([cnt[x] for x in cnt if x != maxxChar])

            if sumOthers > k :
                cnt[s[left]] -= 1
                left += 1

            else :
                longest = right - left + 1
                right += 1
                if right < len(s) :
                    cnt[s[right]] += 1

        return longest

m424 v3 Additional bit of performance.py

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = Counter(s[0])

        longest = min(k, len(s))
        left, right = 0, 0
        while right < len(s) :
            if right - left + 1 <= longest :
                right += 1
                if right < len(s) :
                    cnt[s[right]] += 1
                continue

            maxxChar = max(cnt, key=lambda x: cnt[x])
            sumOthers = sum([cnt[x] for x in cnt if x != maxxChar])

            if sumOthers > k :
                cnt[s[left]] -= 1
                left += 1

            else :
                longest = right - left + 1
                right += 1
                if right < len(s) :
                    cnt[s[right]] += 1

        return longest

m424 v4 Removed O(k) Summations for Math.py

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = Counter(s[0])

        longest = min(k, len(s))
        left, right = 0, 0
        while right < len(s) :
            if right - left + 1 <= longest :
                right += 1
                if right < len(s) :
                    cnt[s[right]] += 1
                continue

            maxxChar = max(cnt, key=lambda x: cnt[x])
            sumOthers = right - left + 1 - cnt[maxxChar]

            if sumOthers > k :
                cnt[s[left]] -= 1
                left += 1

            else :
                longest = right - left + 1
                right += 1
                if right < len(s) :
                    cnt[s[right]] += 1

        return longest

m424 v5 Optimal.py

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = Counter()

        left, right = 0, 0
        maxFreq = 0
        for right in range(len(s)) :
            cnt[s[right]] += 1
            maxFreq = max(maxFreq, cnt[s[right]])
            
            if right - left + 1 - maxFreq > k :
                cnt[s[left]] -= 1
                left += 1

        return right - left + 1