Programming Skills: Permutation in String

[題目]
https://leetcode.com/problems/permutation-in-string/description/

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

給你一兩個string s1,s2，問你s1是否是s2的substring，或是substring的任一種permutation也算。

[思路]

其實這題很像另外一個經典題 :
s2中是否存在一個substring ，等於s1

這種"是否存在"的問題，就是叫你去找s2中有沒有人(下面用target代稱)，長的和s1一樣。

而搞清楚"甚麼叫做一樣"，就是問題的關鍵

一般的狀況，符合以下條件就是"一樣":

s1和target擁有的char，種類和數量一樣
s1和target的char的排列一樣

回到原題
這題看似比經典題難，因為還增加了一個"任一permutation"的條件
但其實比經演題簡單，因為char隨便排都可以，不用考慮上述的條件二。
所以只要滿足

s1和target中擁有的char，種類和數量一樣

看到這邊就該想起之前另一題教過的統計法，用hashtable1紀錄s1中char的種類和數量。
然後用一個大小等於s1的sliding window掃一遍s2，掃瞄過程中也會有一個sliding window對應的hashtable2，然後比對兩個hashtable是否一樣。一樣的時候，就代表兩個人互為permutation。結案 !

[進階思路]
上面最後講到要比對兩個hashtable，這費時O(len(s1))。
而s2中總共有len(s2)-len(s1)+1個target substring，所以總共時間是相乘O(len(s1)*len(s2))。

但有更好的作法可以在O(len(s2))做完。
沒錯讓我們來改進一下"比對hashtable"這件事情。
在掃描s2時，與其建立hashtable2，不如直接操作hashtable1。
具體操作是這樣的:

先用s1初始化hashtable1, 初始化時h['a']=1, h['b']=1，代表s1擁有1個'a'，1個'b'。

接著我們用sliding window掃描s2，每次都會吃入右邊一個，吐出左邊一個。

在吃與吐到字元的時候，把它拿來抵銷hashtable1中字元的數量，並把資訊更新入hashtable1

然後用一個balance count紀錄目前順利抵銷了的數量

A.所以當s2 sliding window向右掃描時，右邊吃入一個'a'，並做--h['a']，

做--h['a']代表嘗試用s2 window中的'a'抵銷s1 table中的'a'。這時有兩種情況：
1.h['a']>=0 : 代表正常地抵銷著，可以把balance count++

而此時h['a']的數字代表(假設是k)，本次抵銷完後, 還剩下k個'a'要找。

2.h['a']<0 : 這代表sliding window本次吃進來的'a'是多餘的，不能拿來抵銷s1中的char，所以不去動balance count

(表示s2 sliding window納入了一個s1中不存在的char，所以不能抵銷)

但依然如實地--h['a']，所以此時h['a']的數字代表(假設是k)，window中有k個不存在s1中的'a'

B.當s2 sliding window向右掃描時，左邊吐出一個'a'，並做++h['a']，

做++h['a']代表s2 window中'a'離開了，無法抵銷s1 table的'a'。這時有兩種情況：
1.h['a']>0 : 我們就知道s2 sliding window吐出了一個s1中的char。
原本用來抵銷的'a'被吐出去了，所以把balance count--

2.h['a']<=0 : ++h['a']後還小於等於0, 表示s2 sliding window吐出去的'a'本就不屬於s1的char

所以balance count不動

最後的關鍵是，在sliding window每一輪移動後，我們檢查balance count==s1.length()

如果相等代表s1內的所有字母都被順利抵銷，代表sliding window目前所框住的substring可以完全抵消s1


    bool checkInclusion(string s1, string s2) {

        int len1=s1.size();
        int len2=s2.size();
        int matchcnt=0;
        unordered_map<char,int> m; 

        for(int i=0;i<len1;i++)
            m[s1[i]]++;

        for(int k=0; k<len2; k++){
            if(k<len1){
                if(--m[s2[k]] >= 0) matchcnt++;
            }
            else{
                if(--m[s2[k]] >= 0) matchcnt++;
                if(++m[s2[k-len1]] > 0) matchcnt--;
            }
            if(matchcnt==len1)   
                return true;
        }
        return false;
    }