# LeetCode Solution, Medium, 567. Permutation in String

# [567. Permutation in String](https://leetcode.com/problems/permutation-in-string/)

### 題目敘述

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

**Constraints:**

- `1 <= s1.length, s2.length <= 10^4`
- `s1` and `s2` consist of lowercase English letters.

#### 題目翻譯

從 `s2` 中找出是否有包含 `s1` 的亂序組合。

### 解法解析

這題最好的解法就是用 Sliding window 的方式來解，可以使用陣列或 Hash Map 的方式來記錄字母的出現次數來做比對。因為是亂序的不需要記住順序。
簡單介紹 Sliding window 的方式。

`s2`：2 3 4 1 2 4 2 4
`s1`：4 1

Sliding window 就是一格一格的滑動過去。
1. 先比對 `s2` 的 index 0 跟 1，亦即 2 3 跟 4 1 比對
2. 然後再滑過去一格 index 1 跟 2，即 3 4 跟 4 1 比對
3. 再滑一格 index 2 跟 3，4 1 跟 4 1 比對，找到了即答案

#### 程式範例

##### Go

```go
func checkInclusion(s1 string, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}

	var s1Map = [26]int{}
	var s2Map = [26]int{}
	for i := 0; i < len(s1); i++ {
		s1Map[s1[i]-'a']++
		s2Map[s2[i]-'a']++
	}

	count := 0
	for i := 0; i < 26; i++ {
		if s1Map[i] == s2Map[i] {
			count++
		}
	}

	for i := 0; i < len(s2)-len(s1); i++ {
		r := s2[i+len(s1)] - 'a'
		l := s2[i] - 'a'

		if count == 26 {
			return true
		}
		s2Map[r]++
		if s1Map[r] == s2Map[r] {
			count++
		} else if s1Map[r]+1 == s2Map[r] {
			count--
		}
		s2Map[l]--
		if s1Map[l] == s2Map[l] {
			count++
		} else if s1Map[l]-1 == s2Map[l] {
			count--
		}
	}

	return count == 26
}
```

##### JavaScript

```javascript
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
    if (s1.length > s2.length) return false;

    const s1Map = new Array(26).fill(0);
    const s2Map = new Array(26).fill(0);
    for (let i = 0; i < s1.length; i++) {
        s1Map[s1[i].charCodeAt(0) - 97]++;
        s2Map[s2[i].charCodeAt(0) - 97]++;
    }

    let count = 0;
    for (let i = 0; i < 26; i++) {
        if (s1Map[i] === s2Map[i]) {
            count++;
        }
    }

    for (let i = 0; i < s2.length - s1.length; i++) {
        const r = s2[i + s1.length].charCodeAt(0) - 97;
        const l = s2[i].charCodeAt(0) - 97;
        if (count === 26) {
            return true;
        }

        s2Map[r]++;
        if (s1Map[r] === s2Map[r]) {
            count++;
        } else if (s1Map[r] + 1 === s2Map[r]) {
            count--;
        }

        s2Map[l]--;
        if (s1Map[l] === s2Map[l]) {
            count++;
        } else if (s1Map[l] - 1 === s2Map[l]) {
            count--;
        }
    }

    return count === 26;
};
```

##### Python

```python
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        s1map = [0] * 26
        s2map = [0] * 26
        for i in range(len(s1)):
            s1map[ord(s1[i]) - ord('a')] += 1
            s2map[ord(s2[i]) - ord('a')] += 1

        count = 0
        for i in range(26):
            if s1map[i] == s2map[i]:
                count += 1

        for i in range(len(s2) - len(s1)):
            r = ord(s2[i + len(s1)]) - ord('a')
            l = ord(s2[i]) - ord('a')
            if count == 26:
                return True
            s2map[r] += 1
            if s2map[r] == s1map[r]:
                count += 1
            elif s2map[r] == s1map[r] + 1:
                count -= 1
            s2map[l] -= 1
            if s2map[l] == s1map[l]:
                count += 1
            elif s2map[l] == s1map[l] - 1:
                count -= 1

        return count == 26
```


## Reference
- https://github.com/Taiwolskit/leetcode/tree/master/Algorithms/567.%20Permutation%20in%20String