12/23/2022 Two Leetcode Questions

[box-lin]

Today Topic: Sliding Window

• 567. Permutation in String
• 424. Longest Repeating Character Replacement

[137thphxx]

567. 超时

     from itertools import permutations
     class Solution:
     def checkInclusion(self, s1: str, s2: str) -> bool:
         if len(s1) > len(s2):
             return False
     
         length1 = len(s1)
         length2 = len(s2)
     
         perms = [''.join(i) for i in permutations(s1)]
     
         if any(exist in s2 for exist in perms):
             return True
         else:
             return False

     可用

     class Solution:
     def checkInclusion(self, s1: str, s2: str) -> bool:
         if len(s1) > len(s2):
             return False
     
         cntr, w = Counter(s1), len(s1)   
         for i in range(len(s2)):
             if s2[i] in cntr: 
                 cntr[s2[i]] -= 1
             if i >= w and s2[i-w] in cntr: 
                 cntr[s2[i-w]] += 1
     
             if all([cntr[i] == 0 for i in cntr]): 
                 return True
     
         return False

[box-lin]

# [567. Permutation in String] 
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        match = [0] * 26
        for ch in s1:
            match[ord(ch)-ord('a')] += 1

        # window setup
        window  = [0] * 26
        winsize = len(s1)
        for i in range(winsize):
            window[ord(s2[i]) - ord('a')] += 1

        if window == match: return True

        # window sliding 
        for i in range(winsize, len(s2)):
            window[ord(s2[i]) - ord('a')] += 1 
            window[ord(s2[i-winsize]) - ord('a')] -= 1
            if window == match:
                return True 
        return False

# [424. Longest Repeating Character Replacement] 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        freqTable = defaultdict(int)
        maxcnt = 0
        ans = 0 
        l = 0 
        for r, ch in enumerate(s):
            freqTable[ch] += 1
            maxcnt = max(maxcnt, freqTable[ch])
            #总长度 - 最大频 = 可调整字符
            while r-l+1 - maxcnt > k:
                freqTable[s[l]] -= 1
                l+=1
            ans = max(ans, r-l+1)
        return ans