# 567 Permutation in String

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

## 1. Question

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

## 2. Implementation

**(1) Two Pointers + Hash**

```java
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        int[] map = new int[256];

        for (char c : s1.toCharArray()) {
            ++map[c];
        }

        int end = 0, start = 0, count = s1.length();

        while (end < s2.length()) {
            if (map[s2.charAt(end)] > 0) {
                --count;
            }
            --map[s2.charAt(end)];
            ++end;

            if (end - start - 1 == s1.length()) {
                if (map[s2.charAt(start)] >= 0) {
                    ++count;
                }
                ++map[s2.charAt(start)];
                ++start;
            }

            if (count == 0) {
                return true;
            }
        }
        return false;
    }
}
```

## 3. Time & Space Complexity

**Two Pointers + Hash:** 时间复杂度O(n), 空间复杂度O(1)