# Python-LeetCode 581 第二招 Sliding Window

「把小小的窗戶推呀推呀推，修改左界，維護不變，答案就出現！」
所謂Sliding window(滑動視窗)是指在處理序列問題時，我們關注在一個$[left,right]$的區域(視窗)，運算過程中我們逐步滑動此視窗並保持住此視窗的某些迴圈不變性。LeetCode中有接近100題有sliding window的標籤，此法與Two pointers有時難以區分。

## 簡單例題
挑選幾題來說明Python的sliding window寫法。先上場的是
[(題目連結) 3. Longest Substring Without Repeating Characters(難度Medium)](https://leetcode.com/problems/longest-substring-without-repeating-characters/)。題目非常簡單：給一個字串$s$，找出不含重複字元的最長子字串長度。

在大方向上，每個可能的解都是一個substring，substring是一個連續區間，我們找出每一個可能右端的最長字串，在所有可能右端中取最大值就是答案。
以右端$right$從前往後逐一掃過，對於$(left,right]$這個視窗區間，維護好以下的迴圈不變性：
**left為視窗內沒有重複的字元的最小左端**。
如何維護呢？
假設前一個右端時此特性是符合的。當右端右移時，如果違反上述不變性，也就是視窗內有重複字元，那麼就必須將左端右移直到沒有重複字元為止。事實上，重複的字元必然是因為剛移入的$s[right]$撞到與視窗內某字元，也就是存在唯一的$j$，滿足 $left<i<right$ and $s[j]==s[right]$，而我們必須把$left$移到$j$才能繼續維持該迴圈不變性。

思考清楚了，程式是簡單的。為了要偵測哪個字元重複了，我們可以用一個紀錄器紀錄視窗內所有字元出現次數(或是否出現)，這裡我們採用一個長度256的list，因為字元的ascii必在0~255之間，當然也可以用字典來做。
注意此處我們用的是$(left,right]$半區間，當然也可以定義為閉區間或開區間。寫題時必須定義好自己的區間端點是否包含，才不會搞錯。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = -1
        cnt = [0]*256 # counter of char
        longest = 0 #global opt
        # sweep right one by one
        for right,ch in enumerate(s):
            p = ord(ch) # ASCII code
            cnt[p] += 1
            while cnt[p] > 1: #repeated
                left += 1 # move step by step
                cnt[ord(s[left])] -= 1
            longest = max(longest, right-left)
        return longest
                

時間複雜度是多少呢？這裡雖然有雙迴圈但是與前一個單元講過的amortized analysis一樣。這裡的$left$與$right$都沒有回頭，時間複雜度是$O(n)$，$n$是字串長度。

講一下**迴圈不變性**這個重要的觀念。
很多人剛學程式時，學了語法面對題目卻不知所措。也許有人說，應該多看題目，多學習資料結構與算法。也對啦，人面對問題時的思考來自分析與歸納，多看多學，你會從過去的經驗歸納出解決面臨的問題。但推理思考也是很重要的。我們可以反過來問一個問題，如果你針對一個問題設計出一支程式，你如何說服別人與你自己，這支程式是對的？
不要只是說：跑了多少測資都是對的。
其實證明的過程就是思考的過程。
複雜的問題與程式當然需要分成很多步驟，但對於一個區段或一個小副程式，答案往往就在**迴圈不變性**，背後的道理其實也就是數學歸納法。
以我們現在這個問題來說，這段程式為什麼是對的，你再回頭去看看上面我們維護的迴圈不變性，如果右端移動前該性質是對的，那麼我們採取的動作就是有維護好該不變性，那根據數學歸納法在任何一個$right$時，他的區間就是最長的，答案就是對的。

再用一個更簡單的例子說明，在一序列中以迴圈找最大值。

imax = s[0]
for p in s[1:]:
    imax = max(imax,p)

這是大部分人剛學程式都會學過的例子。
他為什麼是對的？
我們維護的迴圈不變性是：
$imax$是看到目前為止的最大值。
初始是對的。
若對$s[:i]$是對的，則對$s[:i+1]$也是對的。

在解決問題時，思考我們要維護好什麼迴圈不變性，剩下的是利用語言工具去完成它，這樣設計程式就會比較有脈絡可循，寫出來的程式邏輯也會清晰不紊亂。

### 另一個寫法
上面的範例程式中，我們用計數器紀錄字元是否出現，當重複時，用while迴圈移動左端直到重複消失。看起來有點笨，因為我們明明就已經知道重複的是新右端那個字元呀！那還需要一路慢慢摸過去嗎？其實複雜度沒有甚麼壞，因為那個while迴圈的測試條件成本是低的，如果換個場景那個while條件的測試成本(時間)極高，那就的確不是個好寫法。
我們換一個寫法，大格局不變，我們紀錄每一個字元在視窗內出現的位置，因為只能出現一次，所以就是他最後的位置，叫做$last[\;]$，若值為-1表示沒出現。那麼上面的程式會改成下面的樣子。當重複發生時，我們用一個for迴圈(第9~10行)一股腦兒地將這些位置全部清為-1。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = -1
        last = [-1]*256 # not existing
        longest = 0
        for right,ch in enumerate(s):
            p = ord(ch)
            if last[p] >= 0: # existing in window
                for c in s[left+1:last[p]]: # clear
                    last[ord(c)] = -1
                left = last[p]
            last[p] = right
            longest = max(longest, right-left)
        return longest
                

## 固定視窗長度的範例

前一個例子的左右端區間長度是變來變去的，雖然可以歸類在sliding window，但也可以歸類到雙指標爬行(two pointers)。我們再舉一例，視窗長度是固定的，
[(題目連結) 1456. Maximum Number of Vowels in a Substring of Given Length(難度Medium)](https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/)
本題中，輸入是一個小寫字母組成的字串以及一個整數$k$，要找出長度$k$的子字串最多含有多少個母音。

同樣的，我們關注一個區段，也就是視窗，然後將這個視窗逐步往右推過去，每次我們要做的是計算出視窗內母音的個數，對所有視窗取最大值就是答案。迴圈不變性是
**cnt是視窗內母音的個數**。
對於一個字母是否是母音我們可以用一個 if 取5個判斷式的or，這裡我們聰明一點用集合來判斷。下面是範例程式。

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        d = {'a','e','i','o','u'}
        cnt = 0
        for c in s[:k]: 
            if c in d: cnt += 1
        imax= cnt
        for i in range(k,len(s)):
            if s[i] in d: cnt += 1
            if s[i-k] in d: cnt -= 1
            if cnt>imax: imax = cnt
        return imax

因為視窗是固定長度，所以不需要用兩個變數來維護左右端，我們用一個變數維護右端即可。第5~6行是初始的視窗，先計算視窗內母音個數。第8行開始的迴圈將右端逐步右移，如果移進來一個母音，cnt+1；如果左端移出去一個母音，cnt-1。
時間複雜度顯然是$O(n)$，集合成員判斷可以視作$O(1)$而且他還只有5個。

## 較複雜的例子
再挑一題比較難的。
[(題目連結) 30. Substring with Concatenation of All Words(難度Hard)](https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/)。

這個題目是說有一個可能很長的字串$s$，另外有一個字串陣列$words$，其中$words$裡面的每個字串長度都是$k$，$k\leq 30$。要找的是$s$中有哪些substring剛好是words的permutation。所謂permutation是指$words[i]$與$words[j]$的位置可以交換改變，但每一個$words[i]$內部的字元是不可以重排的。請注意，如範例二的情形，$words$中可能有相同重複的字串。

假設我們先把$words$看成一群整數，$s$看成整數序列，那麼題目就是找出連續的一段是$words$這群整數的排列，所謂排列其實就是每個出現的東西的出現次數一樣，或是說相同的重集合(允許相同元素的集合)。
顯然，一個區間要滿足要求，他的長度必須與$words$一樣，所以用sliding window的概念，固定視窗寬度，紀錄視窗內各個成員的出現次數，只要視窗內沒有不是成員的傢伙，而且成員每個出現次數也不超過該有的次數，那就是每個成員出現次數都剛剛好。

以下是這樣想法寫出來的程式。要把words中的字串轉換成整數，我們使用一個字典。第3行的Counter()是一種dict的子類別，用來計算相同物的數量很方便，當然丟進去的東西必須是可以放進字典的(可雜湊)，例如整數、字串、tuple。

**Python dict 小小說明：** Python的字典很好用，用起來有個小毛病，key值不存在的時候不能取，否則會噴KeyError。defaultdict(XXX)是一種字典，當key值不存在時會給予XXX的default值。例如defaultdict(int)如果key值不存在時就會以int的預設值0來處理，常用的方式有defaultdict(int)，defaultdict(list)與defaultlist(set)，也可以自訂類別。

回到我們的問題。我們根據Counter()的結果，把每一個$words$中出現的字串，對應到一個0,1,2...的整數$idx$，並儲存他在$words$中出現的次數$req$，這是第4~11行做的事情。

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:            
        d = Counter(words)
        idx = {} # new index of each word
        req = [] # number of the word we need
        m = 0 # num of different words
        for t in d:
            idx[t] = m
            req.append(d[t])
            m += 1
        #endfor build dict
        n,k = len(s),len(words[0])
        ans = []
        for start in range(k): # starting position
            seq = [] # sequence of keys
            for p in range(start,n-k+1,k): # cut every k char 
                t = s[p:p+k]
                if t not in idx:
                    seq.append(-1)
                else:
                    seq.append(idx[t])
            # sliding windows
            occ = [0]*m
            left = 0 # window = [left,right]
            for right,x in enumerate(seq):
                if x<0: # clear occurence
                    for i in range(left,right):
                        occ[seq[i]] -= 1
                    left = right+1
                    continue
                occ[x] += 1
                while occ[x] > req[x]: # too many
                    occ[seq[left]] -= 1
                    left += 1
                if right-left+1 == len(words): # found
                    ans.append(start+left*k)
            #endfor sliding windows
        # end for starting position
        return ans
                                 

接下來第14行開始的外迴圈在嘗試所有可能的起始位置，因為我們要的固然是固定長度的區間，但起始位置可能是$0$ ~ $k-1$的各種可能。
第15~21行每隔$k$就切一段下來，對照轉換成代表的整數，如果不存在則以-1表示。
第23行$occ$表示出現次數，然後開始sliding window，第26 ~ 30行處理不存在時清空的動作，第32~34行處理出現次數超過時，移動左端的動作。當沒有不存在的而且每個次數沒超過時，長度如果是一樣，就表示是個答案了。
時間複雜度是$O(nk+mk)$，$n$是$s$的長度而$m$是$words$內字串的個數。

### 另一種寫法
上面的寫法是分兩大步驟的，先做轉換再掃描整數序列。我們也可以把它合併，就不做轉換的動作，直接用Counter()的結果當作倒數計數器，但因為有多次要做，每次要複製一份下來(第7行)，這是下面這支範例程式的寫法，細節就不再重複說明。

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:            
        d = Counter(words)
        n,k = len(s),len(words[0])
        ans = []
        for start in range(k): # starting position
            cnt = d.copy()
            left = start # sliding windows
            for right in range(start,n-k+1,k): # cut every k char 
                t = s[right:right+k]
                if t not in cnt:
                    while left<right: # clear
                        cnt[s[left:left+k]] += 1
                        left += k
                    left += k
                    continue
                cnt[t] -= 1
                while cnt[t] < 0: # too many
                    cnt[s[left:left+k]] += 1
                    left += k
                if right-left+k == len(words)*k: # found
                    ans.append(left)
            #endfor sliding windows
        # end for starting position
        return ans

## 結語

找子字串或在序列中找區間時，經常可以想想看是否適用sliding window的方式，當然，經常會搭配一些計數器或其他技巧。它的正確性通常都可以用迴圈不變性去想。**證明的方法，就是思考的路徑**。
如果是字串類的問題，字典是很常用的工具，LeetCode裡面非常多需要字典的題目，也非常多字串的題目。
Python在這方面其實是比其他語言佔優勢的。其中一點是Python的字串(與list)的slicing寫起來非常舒服，它甚至可以用負的index表示倒數的位置。另外一點，Python內建的字串搜尋string.find()是非常快速的。這些我們應該會在其他單元再看到。