567. Permutation in String (M)

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 <= 104

• s1 and s2 consist of lowercase English letters.

Solution:

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

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

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

// 判断 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:

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

先扫一遍字符串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;
    }
}