Back to solutions

Permutation in String

MediumSliding Window

Return true if s2 contains a permutation of s1 as a contiguous substring.

Open problem
Constraints
  • 1 <= s1.length, s2.length <= 10^4
  • Lowercase letters

Fixed-size sliding window of counts

Time O(n)Space O(1)

Maintain a window of length |s1| over s2 and compare letter counts with s1. Slide the window by adding the new character and removing the old, checking for a match each step.

#include <bits/stdc++.h>
using namespace std;

bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;
    array<int, 26> need{}, win{};
    for (char c : s1) need[c - 'a']++;
    for (int i = 0; i < (int)s2.size(); i++) {
        win[s2[i] - 'a']++;
        if (i >= (int)s1.size()) win[s2[i - s1.size()] - 'a']--;
        if (win == need) return true;
    }
    return false;
}