567. Permutation in String

https://leetcode.com/problems/permutation-in-string/description/

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

Thoughts

s2是否存在s1的permutation。permutation => 静态窗口。用freq map统计s1的元素出现次数，然后维持一个s1 size的窗口扫描s2，当遇到元素与map中的元素相同时，把相应的freq++, 同时把窗口最前面元素剔除并把(如果有的话)相应的--，并用cnt记录freq为0的个数。 当cnt == len(s1)，表明这一段刚好有且仅有s1中所有元素。

Code

/*
 * @lc app=leetcode id=567 lang=cpp
 *
 * [567] Permutation in String
 */

// @lc code=start
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
       const int M = s1.length(), N = s2.length();
       if (M > N) return false;
       vector<int> freq(26, 0);
       for (const auto c : s1) --freq[c - 'a']; 
       int cnt = 0;
       for (int i = 0; i < M; ++i) {
           const auto k = s2[i] - 'a';
           ++freq[k];
           if (freq[k] <= 0) ++cnt;
       }
       if (cnt == M) return true;
       for (int l = 0, r = M; r < N; ++r, ++l) {
           ++freq[s2[r] - 'a'];
           if (freq[s2[r] - 'a'] <= 0) ++cnt;
           if (freq[s2[l] - 'a'] <= 0) --cnt;
           --freq[s2[l] - 'a'];
           if (cnt == M) return true;
       }
       return false;
    }
};
// @lc code=end

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] window = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            // 滑动窗口: 判断窗口包含的元素是否和s2包含的元素相同
            // 当r新遇到一个字符, 看作从滑动窗口中取出一个相同的字符, 并把l的字符还回去
            // 正值表示该字符还没有被取完
            // 负值表示该字符取过投了.
            window[s1.charAt(i) - 'a']++;
        }

        int l = 0, r = 0;
        int targetCount = s1.length(), curCount = 0;
        for (r = 0; r < s1.length(); r++) {
            window[s2.charAt(r) - 'a']--; 
            if (window[s2.charAt(r) - 'a'] >= 0) {
                curCount++;
            }
        }

        if (curCount == targetCount) {
            return true;
        }

        while (r < s2.length()) {
            // tick the left out
            if (window[s2.charAt(l) - 'a'] >= 0) {
                curCount--;
            }
            window[s2.charAt(l) - 'a']++;
            l++;
            // feed the new member
            window[s2.charAt(r) - 'a']--;
            if (window[s2.charAt(r) - 'a'] >= 0) {
                curCount++;
            }
            r++;
            if (curCount == targetCount) {
                return true;
            }
        }

        return false;
    }

}

Analysis

时间复杂度O(n), 空间O(1).