[/dsa/leetcode]

567 - Permutation in String

Thursday, 17 September 2026

<medium> [problem]

Fixed size sliding window with letter counts, tracking how many letters of s1 currently have the right count in the window.

{hash table}{string}{sliding window}

Problem

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 a substring of s2.

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains "ba", a permutation of s1

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

  • 1 <= s1.length, s2.length <= 10^4
  • s1 and s2 consist of lowercase English letters

Approach

A permutation of s1 is just the same letters in any order, so we look for a part of s2 with the same length as s1 that has exactly the same letter counts. Move a window of that length across s2, like in 2461, keeping a count of each letter inside it. Instead of comparing all the counts at every step, keep a number matches: how many of s1’s letters have the right count in the window right now. When the window moves, only the letter leaving and the letter entering change, so we only fix matches for those two. If matches equals the number of different letters in s1, the window is a permutation. Other letters don’t need checking, because the window and s1 are the same length, so there’s no room left for them.

Use mp1.find rather than mp1[c] for s1’s counts. mp1[c] would add letters that aren’t in s1 and change mp1.size().

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> mp1, mp2;
        const int n = s1.length(), m = s2.length();
        if (n > m) return false;

        for (int i = 0; i < n; i++) {
            mp1[s1[i]]++;
            mp2[s2[i]]++;
        }

        const int need = mp1.size();
        int matches = 0;
        for (auto& [c, v] : mp1) {
            if (mp2[c] == v) matches++;
        }
        if (matches == need) return true;

        for (int i = 1; i <= m - n; i++) {
            char out = s2[i - 1], in = s2[i + n - 1];

            auto it = mp1.find(out);
            if (it != mp1.end() && mp2[out] == it->second) matches--;
            --mp2[out];
            if (it != mp1.end() && mp2[out] == it->second) matches++;

            it = mp1.find(in);
            if (it != mp1.end() && mp2[in] == it->second) matches--;
            ++mp2[in];
            if (it != mp1.end() && mp2[in] == it->second) matches++;

            if (matches == need) return true;
        }
        return false;
    }
};
  • time: O(n + m)
  • space: O(1) - at most 26 letters in each map
quantinium © 2026