Conquer this problem using Python && sliding window && dictionary && heap


  • 0

    Idea:
    Step 1. Just welcome the new comer.
    Step 2. Relocation the starting point trying to make the window a largest and valid expanded window.
    Step 3. Update the answer

    class Solution(object):
        def characterReplacement(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            window, strt, charcnt, ans = [], 0, {}, 0
            for i in xrange(len(s)):
                #Step 1
                tmp = None
                if s[i] in charcnt:
                    tmp = charcnt[s[i]]
                    tmp[0] -= 1
                else:
                    tmp = [-1, s[i]]
                    charcnt[s[i]] = tmp
                    heapq.heappush(window, tmp)
                #Step 2
                while (i - strt + 1) + (heapq.nsmallest(1, window))[0][0] > k:
                    charcnt[s[strt]][0] += 1
                    strt += 1
                #Step 3
                ans = max(ans, 1 + i - strt)
            return ans
    

Log in to reply
 

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