Leetcode 1456. Maximum Number of Vowels in a Substring of Given Length (python)

题目

解法1：stack

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        if len(s)<k:
            return 0
        candidates = ['a','e','i','o','u']
        ans = 0
        window = collections.deque()
        for c in s[:k]:
            if c in candidates:
                ans += 1
            window.append(c)
        
        p2 = k
        max_ans = ans
        while p2<len(s):
            if s[p2] in candidates:
                ans += 1
            window.append(s[p2])
            left = window.popleft()
            if left in candidates:
                ans -= 1
            
            max_ans = max(max_ans,ans)
            #print(window)
            if max_ans == k:
                return k
            p2 += 1
        
        return max_ans

解法2：滑窗

实际上只需要管头尾两个元素进行相应的+1和-1就可以了，上面stack的pop操作直接通过计算index得到

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        candidates = ['a','e','i','o','u']
        arr = []
        for c in s:
            if c in candidates:
                arr.append(1)
            else:
                arr.append(0)
        
        count = 0
        for num in arr[:k]:
            if num == 1:
                count += 1 
        
        ans = count
        for i in range(k,len(arr)):
            count = count + arr[i] - arr[i-k]
            ans = max(ans,count)
            if ans == k:
                return k
        return ans