###### tags: `Leetcode` `medium` `sliding window` `python` `c++`

# 567. Permutation in String

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

## 題目:
Given two strings ```s1``` and ```s2```, return ```true``` if ```s2``` contains a permutation of ```s1```, or ```false``` otherwise.

In other words, return ```true``` if one of ```s1```'s permutations is the substring of ```s2```.

**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

## 解題想法:
* 此題為給兩個字串，判斷s2中是否包含s1相同結構的連續子字串
* 相同類型[438. Find All Anagrams in a String](/6f6zLrrtTx2xzZr7lJg5SQ)
* 使用Silding Window:
* 初始:
* head=0
* tail=0
* cur=collections.Counter(): 紀錄當前累計的種類數量
* countS1=collections.Counter(s1): 紀錄s1中字符種類數量
* while判斷:
* cur[s2[tail]]+=1
* if 長度==len(s1):
* if cur==countS1:
* return True
* 刪s2[head]
* head+=1
* tail+=1
* return False

## Python_Sol1:

#同P438
from collections import Counter
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        #slide window
        #best case
        if len(s1)>len(s2):
            return False
        head=0
        tail=0
        cur=Counter()
        countS1=Counter(s1) #先存好
        while tail<len(s2):
            cur[s2[tail]]+=1
            if tail-head+1==len(s1):
                if cur==countS1:
                    return True
                cur[s2[head]]-=1
                if cur[s2[head]]==0: #0的話 要刪掉幽靈戶口
                    del cur[s2[head]]
                head+=1
            tail+=1
        return False
    
result=Solution()
ans=result.checkInclusion(s1 = "ab", s2 = "eidbaooo")
print(ans)

## Python_Sol2:
* 因為都是小寫字母，用array存26個位置比較即可

class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1)>len(s2):
            return False
        l1=[0 for _ in range(26)]
        l2=[0 for _ in range(26)]
        for i in range(len(s1)):
            #ord(a)=97
            l1[ord(s1[i])-97]+=1
            l2[ord(s2[i])-97]+=1
        #first match:
        if l1==l2:
            return True
        #slide window
        for head in range(len(s2)-len(s1)): #從0~(len(s2)-len(s1)-1)
            l2[ord(s2[head])-97]-=1 #去頭
            l2[ord(s2[head+len(s1)])-97]+=1 #加新尾巴
            if l1==l2:
                return True
        return False
    
result=Solution()
ans=result.checkInclusion(s1 = "ab", s2 = "eidbaooo")
print(ans)

## C++_Sol1:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n1=s1.size(), n2=s2.size();
        if (n1>n2)
            return false;
        int head=0, tail=0;
        unordered_map<int, int> dic1, cur;
        for (char item: s1){
            dic1[item]+=1;
        }
        while (tail<n2){
            cur[s2[tail]]+=1;
            if ((tail-head+1)==n1){
                if (dic1==cur)
                    return true;
                cur[s2[head]]-=1;
                if (cur[s2[head]]==0)
                    cur.erase(s2[head]);
                head+=1;
            }
            tail+=1;
        }
        return false;
    }
};

## C++_Sol2:

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n1=s1.size(), n2=s2.size();
        if (n1>n2)
            return false;
        vector<int> l1(26,0);
        vector<int> l2(26,0);
        for (int i=0; i<n1; i++){
            l1[int(s1[i])-int('a')]+=1;
            l2[int(s2[i])-int('a')]+=1;
        }
        if (l1==l2)
            return true;
        for (int head=0; head<n2-n1; head++){
            l2[int(s2[head])-int('a')]-=1;
            l2[int(s2[head+n1])-int('a')]+=1;
            if (l1==l2)
                return true;
        }
        return false;
    }
};