> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/6.array/567.-permutation-in-string-m.md).

# 567. Permutation in String (M)

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 <= 104`
* `s1` and `s2` consist of lowercase English letters.

### Solution:

**Version 1:**\
注意哦，输入的 `s1` 是可以包含重复字符的，所以这个题难度不小。

这种题目，是明显的滑动窗口算法，**相当给你一个 `S` 和一个 `T`，请问你 `S` 中是否存在一个子串，包含 `T` 中所有字符且不包含其他字符**？

首先，先复制粘贴之前的算法框架代码，然后明确刚才提出的 4 个问题，即可写出这道题的答案：

```cpp
// 判断 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return false;
}


JAVA Version:
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        
        Map<Character,Integer> needs = new HashMap<Character,Integer>();
        HashMap<Character, Integer> windows = new HashMap<Character, Integer>();
        for(int i = 0;i< s1.length(); i++)
        {
            needs.put(s1.charAt(i), needs.getOrDefault(s1.charAt(i), 0)+1);
        }
        
        char[] elements= s2.toCharArray();
        int windowSize = s1.length();
        int start = 0; 
        int end = 0;
        int validLetter = 0;
        while(end< s2.length())
        {
            char currentEnd = s2.charAt(end);
            end++;
            if(needs.containsKey(currentEnd))
            {
                windows.put(currentEnd, windows.getOrDefault(currentEnd, 0)+1);
                if(needs.get(currentEnd).equals(windows.get(currentEnd)))
                {
                    validLetter++;
                }
            }
            while(validLetter == needs.size())
            {
                if(end-start == s1.length()) return true;
                char currentStart = s2.charAt(start);
                start++;
                if(needs.containsKey(currentStart))
                {
                    if(needs.get(currentStart).equals(windows.get(currentStart)))
                    {
                        validLetter--;
                    }
                    windows.put(currentStart, windows.get(currentStart)-1);
                }
                
            }
        }
        return false;
        
    }
}
```

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：

1、本题移动 `left` 缩小窗口的时机是窗口大小大于 `t.size()` 时，应为排列嘛，显然长度应该是一样的。

2、当发现 `valid == need.size()` 时，就说明窗口中就是一个合法的排列，所以立即返回 `true`。

至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

**Version 2:**&#x20;

<https://www.jiuzhang.com/problem/permutation-in-string/><br>

先扫一遍字符串s1，统计各个字母的个数，取s2前s1长度个字符，匹配个数是否相符，若不相符，去除最前面的字符，加入后一个字符，重新比对，直至个数匹配，或扫描完s2。

```
public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2) return false;
        
        int[] count = new int[26];
        for (int i = 0; i < len1; i++) {
            count[s1.charAt(i) - 'a']++;
            count[s2.charAt(i) - 'a']--;
        }
        if (allZero(count)) return true;
        
        for (int i = len1; i < len2; i++) {
            count[s2.charAt(i) - 'a']--;
            count[s2.charAt(i - len1) - 'a']++;
            if (allZero(count)) return true;
        }
        
        return false;
    }
    
    private boolean allZero(int[] count) {
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) return false;
        }
        return true;
    }
}
```