567. Permutation in String

Description

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.

---

Solutions

Solution 1

Intuition

Code

class Solution {
public:
    unordered_map<char, int> map1, map2;
    bool check(char& c) {
        if (map1.count(c) && map1[c] == map2[c]) {
            return true;
        }
        return false;
    }
    bool checkInclusion(string s1, string s2) {
        for (char& c : s1) {
            map1[c]++;
        }
        for (int i = 0, j = 0, cnt = 0; i < s2.size(); i++) {
            if (check(s2[i])) cnt--;
            map2[s2[i]]++;
            if (check(s2[i])) cnt++;
            if (i - j == s1.size()) {
                if (check(s2[j])) cnt--;
                map2[s2[j]]--;
                if (check(s2[j])) cnt++;
                j++;
            }
            if (cnt == map1.size()) return true;
        }
        return false;
    }
};

Complexity

• Time: O(n)
• Space: O(n)

---