# Leetcode 567. Permutation in String
###### tags: `leetcode` `daily`

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

# Method 1 Two pointer
:::info
:bulb: **作法講解**:
1. scan string s1, record 'a'~'z' count stored in vector<int> v1.
2. using left, i two pointer to scan string s2,
store range [left...i] character in s2 in vector<int> v2,
for each index i, increment s2[i] character in v2.
if v2 > v1, decrement s2[left] character in v2, and left plus 1,
if i - left + 1 is equal s1 size, then we can say the range left to i in s2 is
permutation of s1.
:::

:::info
:bulb: **well explained**:
reference: https://leetcode.com/problems/permutation-in-string/solutions/1762469/c-sliding-window-optimized-well-explained/
:::

TC: O(N) SC: O(N)
:::spoiler 完整程式碼

class Solution {
public:
    bool check_cnt_over(vector<int> &cnt1, vector<int> &cnt2) 
    {
        for(int i = 0 ; i < 26 ; i++) {
            if(cnt2[i] > cnt1[i]) {
                return true;
            }
        }
        return false;
    }
    bool checkInclusion(string s1, string s2) {
        vector<int> cnt1(26, 0);
        vector<int> cnt2(26, 0);
        int l = 0;

        for(char c : s1) {
            cnt1[c-'a']++;
        }

        for(int i = 0 ; i < s2.size(); i++) {
            cnt2[s2[i]-'a']++;

            while(check_cnt_over(cnt1, cnt2)) {
                cnt2[s2[l]-'a']--;
                l++;
            }

            if((i - l + 1) == s1.size()) {
                return true;
            }
        }
        return false;
    }
};

:::

# Method 2 Prefix Sum
作法講解:

1. scan each character in s1, and stored each lowercase letter count into vector<int> cnt1,
2. using prefix sum concept, record each index string s2, each lowercase letter count,
stored into vector<vector<int>> cnt2.
the format is cnt2[index]['a'~'z'].
3. we can check for each index in s2, when index is bigger than s1 size
we use cnt2[idx] - cnt2[index - s1.size] generate vector diff_cnt, diff_cnt size is 26,
compare cnt1 and diff_cnt, if diff_cnt is the same as cnt1, we can say range (index-s1.size)~index in s2 is permutation of s1.
4. if we scan all of index of s2, we can not find any index is match to cnt1,
we can say s2 has not contains substring permutation of s1.

TC: O(N) SC: O(N)
:::spoiler 完整程式碼

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n1 = s1.size();
        int n2 = s2.size();
        vector<vector<int>> cnt2(s2.size()+1, vector<int>(26, 0));
        vector<int> cnt1(26, 0);

        for(char c : s1) {
            cnt1[c-'a']++;
        }
        for(int i = 0 ; i < n2; i++) {
            cnt2[i+1] = cnt2[i];
            cnt2[i+1][s2[i]-'a']++;
            
            if(i >= (n1-1)) {
                int j = 0;
                while(j < 26) {
                    if(cnt1[j] != (cnt2[i+1][j] - cnt2[i + 1 - n1][j])) {
                        break;
                    }
                    j++;
                }
                if(j == 26) {
                    return true;
                }
            }
        }
        return false;
    }
};

:::