# 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/6.array/567.-permutation-in-string-m.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.