Python O(n) sliding window


  • 1

    Here i and j are the left and right boundaries of our window, and best is the best candidate to form the longest repeating substring. Also I used a counter called count to store all the number of all characters in current window. (Can use a list instead, I'm just kind of lazy...)

    Every time when we explore a new character s[j], we increment count[s[j]] by 1 first. Then, we pick the best candidates we have. Since we only update count[s[j]] in current loop, best = max(best, count[s[j]]). As long as our window length j - i + 1 is smaller or equal to best + k, we keep exploring new character. Otherwise, we know we have to update our left boundary i cause we've run out of our budget k.

    class Solution(object):
        def characterReplacement(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            count = collections.Counter()
            best = i = 0
            for j in range(len(s)):
                count[s[j]] += 1
                best = max(best, count[s[j]])
                if best + k < j - i + 1:
                    count[s[i]] -= 1
                    i += 1
            return len(s) - i
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.