class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        count, table = 0, {'a', 'e', 'i', 'o', 'u'}
        for a in s[:k]:
            if a in table: count += 1
        res = count
        for i in range(len(s)-k):
            if s[i] in table: count -= 1
            if s[i+k] in table: count += 1
            if res == k: break
            elif res < count:
                res = count
        return res

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [0] * (K+W)
        # 概率确定
        dp[K:N+1] = [1] * (N-K+1)
        sum_ = (N-K+1)
        # 递推计算概率
        for i in range(K-1, -1, -1):
            dp[i] = sum_ / W
            sum_ += (dp[i] - dp[W+i])
        return dp[0]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        from collections import defaultdict, Counter
        m, n = len(s), len(p)
        window, need = defaultdict(int), Counter(p)
        i = j = 0
        res = []
        for c in s[:n]:
            if c in need: window[c] += 1
        if window == need: res.append(0)
        for i in range(m-n):
            if   s[i] in need:   window[s[i]] -= 1
            if s[i+n] in need: window[s[i+n]] += 1
            if window == need: res.append(i+1)
        return res

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ns, nt = len(s), len(t)
        # 确定有解
        if ns < nt: return ""
        # 计数检验
        dictS, need = collections.Counter(s), collections.Counter(t)
        for key, value in need.items():
            if dictS[key] < value: return ""
        # s 与 t 元素一样
        if ns == nt: return s

        # 滑动窗口
        window = defaultdict(lambda: 0) # 初始化空字典
        left, right, valid, length = 0, 0, 0, ns+1
        while right < ns:
            # 移动右边界
            temp = s[right]
            # 判断
            if temp in need:
                window[temp] += 1
                if window[temp] <= need[temp]: valid += 1
            right += 1 # 右边界右移
            # 缩小左边界
            while valid == nt:
                # 判断 + 记录
                if right - left < length: start, length = left, right - left
                if length == len(t): return s[start : start+length] # 提前结束
                temp = s[left]
                if temp in need:
                    if window[temp] == need[temp]: valid -= 1
                    window[temp] -= 1
                left += 1
        return s[start : start+length]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 双端队列
        d = collections.deque()
        # 初始化窗口
        for num in nums[:k]:
            while d and d[-1] < num: d.pop()
            d.append(num)
        res = [d[0]]
        # 滑动窗口
        for j in range(k, len(nums)):
            if nums[j-k] == d[0]: d.popleft()
            while d and d[-1] < nums[j]: d.pop()
            d.append(nums[j])
            res.append(d[0])
        return res

class Solution:
    def lengthOfLongestSubstring(self, s):
        res = left = right = 0
        hashMap = {}
        while right < len(s):
            if s[right] in hashMap:
                res = max(res, right-left)
                left = max(left, hashMap[s[right]])
            hashMap[s[right]] = right+1
            right += 1
        res = max(res, right-left)
        return res

s = "abcabcbb"
# s = "bbbbb"
# s = "pwwkew"
# s = ""
# s = " "
# s = "ab"
# s = "abba"

mat = Solution()
mat.lengthOfLongestSubstring(s)