567

567. Permutation in String (Medium)

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.

Companies:
Yandex, Amazon, Oracle, Facebook, Bloomberg

Related Topics:
Hash Table, Two Pointers, String, Sliding Window

Similar Questions:

• Minimum Window Substring (Hard)
• Find All Anagrams in a String (Medium)

Solution 1. Fixed-length Sliding Window

Store the counts of letters of a in cnts array.

• When we consume a letter b[i], we decrement its count.
• When we pop a letter b[i - N], we increment its count. We start popping when i - N >= 0 to make sure the sliding window is at most as long as a.

Once all the counts in cnts array are zeros, we return true. If we reached end of array and still haven't clear out the cnts, return false.

The time complexity is O(26 * S2) = O(S2).

// OJ: https://leetcode.com/problems/permutation-in-string/
// Author: github.com/lzl124631x
// Time: O(B)
// Space: O(1)
class Solution {
public:
    bool checkInclusion(string a, string b) {
        if (a.size() > b.size()) return false;
        int N = a.size(), cnts[26] = {};
        for (char c : a) cnts[c - 'a']++;
        for (int i = 0; i < b.size(); ++i) {
            cnts[b[i] - 'a']--;
            if (i - N >= 0) cnts[b[i - N] - 'a']++;
            bool match = true;
            for (int j = 0; j < 26 && match; ++j) {
                if (cnts[j]) match = false;
            }
            if (match) return true;
        }
        return false;
    }
};

Solution 2. Fixed-length Sliding Window

Similar to Solution 1, we keep a sliding window of size a.size(). Instead of checking the count for 26 characters, we just use a matched variable to store the number of matched characters within the sliding window.

// OJ: https://leetcode.com/problems/permutation-in-string/
// Author: github.com/lzl124631x
// Time: O(B)
// Space: O(1)
class Solution {
public:
    bool checkInclusion(string a, string b) {
        if (a.size() > b.size()) return false;
        int cnt[26] = {}, matched = a.size(), N = a.size();
        for (char c : a) cnt[c - 'a']++;
        for (int i = 0; i < b.size(); ++i) {
            if (i >= N) matched += cnt[b[i - N] - 'a']++ >= 0;
            matched -= cnt[b[i] - 'a']-- > 0;
            if (!matched) return true;
        }
        return false;
    }
};

Solution 3. Variable-length Sliding Window

We keep the counts of letters of s1 in goal array. And we use two pointers i and j to consume s2, and store the counts of letters within range [i, j) in cnt array.

1. We keep incrementing j and the corresponding count cnt[s2[j]] until it reaches the end or cnt[s2[j]] + 1 <= goal[s2[j]]. Let X be s2[j] then X is the letter we don't want to consume.
2. If the gap between i and j is the length of s1, then we've found match and just return true.
3. Since s2[j] is unwanted, we keep popping s2[i] by incrementing i until s2[i] == s2[j], meanwhile, we decrement cnt[s2[i]].
4. Now s[i] and s[j] are all pointing to the unwanted letter X, increment i and j both so that the cnt[X] will be unchanged. Go to Step 1 until j reaches end.

// OJ: https://leetcode.com/problems/permutation-in-string/
// Author: github.com/lzl124631x
// Time: O(S2)
// Space: O(1)
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int M = s1.size(), N = s2.size(), i = 0, j = 0, goal[26] = {0}, cnt[26] = {0};
        for (char c : s1) goal[c - 'a']++;
        for (; j < N; ++i, ++j) {
            while (j < N && cnt[s2[j] - 'a'] + 1 <= goal[s2[j] - 'a']) cnt[s2[j++] - 'a']++;
            if (j - i == M) return true;
            while (j < N && i < j && s2[i] != s2[j]) cnt[s2[i++] - 'a']--;
        }
        return false;
    }
};

Or

// OJ: https://leetcode.com/problems/permutation-in-string/
// Author: github.com/lzl124631x
// Time: O(B)
// Space: O(1)
class Solution {
public:
    bool checkInclusion(string a, string b) {
        if (a.size() > b.size()) return false;
        int cnt[26] = {};
        for (char c : a) cnt[c - 'a']++;
        for (int i = 0, j = 0; j < b.size(); ++j) {
            if (--cnt[b[j] - 'a'] < 0) { // We can't have this `b[j]` in the window
                while (b[i] != b[j]) cnt[b[i++] - 'a']++; // keep skipping until `b[i] == b[j]`
                cnt[b[i++] - 'a']++; // remove `b[i]` from the window
            }
            if (j - i + 1 == a.size()) return true; // If the window has the same length as `a`, return true
        }
        return false;
    }
};