« Back

Longest Repeating Character Replacement

LeetCode

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.

Initial attempt

Time spent: 1h 20m | Runtime: 87.80% | Memory: 80.26%

Given a window [start, end], a count dict of the characters, and the frequency of the most common character, how can we evaluate those same values for [start + 1, end]?

We don't need to solve this problem since the size of the window never needs to decrease. We're constantly looking to expand the window and may encounter "invalid" windows in our search.

Intuition

Solution

Cleaned up code

Time spent: 8m | Runtime: 77.37% | Memory: 99.42%

import collections


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = collections.defaultdict(int)
        start = 0
        most_frequent = 0
        longest_length = 0
        for end in range(len(s)):
            counts[s[end]] += 1
            most_frequent = max(most_frequent, counts[s[end]])

            # If window size is greater than allowed, contract it.
            if end - start + 1 > most_frequent + k:
                counts[s[start]] -= 1
                start += 1

            longest_length = max(longest_length, end - start + 1)
        return longest_length