Consise Python sliding window


  • 7

    Re: [Sliding window](similar to finding longest substring with k distinct characters)

    Similar idea in Python but allowing any character, not just uppercase English letters [Updated based on comments below]:

    def characterReplacement(self, s, k):
        res = lo = hi = 0
        counts = collections.Counter()
        for hi in range(1, len(s)+1):
            counts[s[hi-1]] += 1
            max_char_n = counts.most_common(1)[0][1]
            if hi - lo - max_char_n > k:
                counts[s[lo]] -= 1
                lo += 1
        return hi - lo
    

    [Original code in order to understand comment from @StefanPochmann was:]

    def characterReplacement(self, s, k):
        res = lo = 0
        counts = collections.Counter()
        for hi in range(len(s)):
            counts[s[hi]] += 1
            max_char_n = counts.most_common(1)[0][1]
            while (hi - lo - max_char_n + 1 > k):
                counts[s[lo]] -= 1
                lo += 1
            res = max(res, hi - lo + 1)
        return res
    

  • 5

    I don't think you need while, because from one for-loop iteration to the next, hi - lo - max_char_n + 1 can grow by at most 1, and each while-loop iteration decreases it by 1. So you can also use if instead. It also means that your window never shrinks, so you can just return the length of the final window:

    def characterReplacement(self, s, k):
        res = lo = 0
        counts = collections.Counter()
        for hi in range(len(s)):
            counts[s[hi]] += 1
            max_char_n = counts.most_common(1)[0][1]
            if hi - lo - max_char_n + 1 > k:
                counts[s[lo]] -= 1
                lo += 1
        return hi - lo + 1
    

    Only problem would be if s were the empty string, but while the problem doesn't rule that out, it's also not in the test suite. Anyway, the C++ solution I made out of it doesn't have that problem and is also a bit shorter.


  • 2

    With some small changes your Python solution could also handle the empty string case:

    def characterReplacement(self, s, k):
        res = lo = hi = 0
        counts = collections.Counter()
        for hi in range(1, len(s)+1):
            counts[s[hi-1]] += 1
            max_char_n = counts.most_common(1)[0][1]
            if hi - lo - max_char_n > k:
                counts[s[lo]] -= 1
                lo += 1
        return hi - lo
    

    But as of now it is the OJ who fails if you pass it the empty string as a test case :-)


  • 0

    Same Solution. This is my code!

    class Solution(object):
        def characterReplacement(self, s, k):
            h = {}
            i, j, ans = 0, 0, 0
            while j < len(s):
                h[s[j]] = h.get(s[j],0) + 1
                while j-i+1-max(h.values()) > k:
                    h[s[i]] -= 1
                    i += 1
                ans = max(ans,j-i+1)
                j += 1
            return ans

  • 0
    Z

    @dalwise @StefanPochmann is this a O(n^2) algorithm?


  • 0

    @zhongyuan9817 The updated algorithm is just O(n)


  • 0
    Z

    @haolexiao Hi, thank you for your response, which one are you talking about? I think both algorithms in this post are O(n^2)


Log in to reply
 

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