Permutation in String — Fixed Sliding Window

What does it solve?

Given a pattern P and a string S, decide whether any permutation of P appears as a contiguous substring of S. A permutation is just an anagram: same characters, any order.

Key insight: any anagram of P has length |P| and the exact same character counts. So slide a window of fixed width |P| across S: on each step add the entering char and drop the leaving one, and check if the window's frequency map equals P's. Comparing counts in O(1) with a running match counter gives O(N).

The core idea

Complexity

Time complexity

O(N + M)

N = |S|, M = |P|. The window slides once across S. Each add/remove updates a running match counter in O(1), no per-step map comparison.

Space complexity

O(K)

Two frequency arrays over the distinct characters. K = alphabet size (26 for lowercase letters), so effectively O(1).

Examples & edge cases

Live animation — fixed window of width |P| sliding across S

inside window entering (right) leaving (left) char needed by P window is an anagram ✓

String S — window [left … right], width |P| —

Character counts — window vs P

left = — right = — matches = — found = —

Step — of —

left pointer

—

window start

right pointer

—

window end

matches

—

counts that agree

Anagram found?

—

scanning…

Select an example and press Play to start.

✓ Answer: —

Speed Medium

Step-by-step table

Step	Phase	left	right	+ in	− out	window	Matches	Anagram?

C++ implementation

permutation_in_string.cpp

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

// True if some permutation of p is a substring of s
bool checkInclusion(string p, string s) {
    int k = p.size(), n = s.size();
    if (k > n) return false;

    int need[26] = {}, win[26] = {};
    for (char c : p) need[c - 'a']++;

    // matches = how many of the 26 letters have equal counts
    for (int right = 0; right < n; right++) {
        win[s[right] - 'a']++;
        if (right >= k) win[s[right - k] - 'a']--; // drop the char leaving the window

        if (right >= k - 1) {                    // window is full width k
            bool ok = true;
            for (int c = 0; c < 26; c++)
                if (win[c] != need[c]) { ok = false; break; }
            if (ok) return true;
        }
    }
    return false;
}

int main() {
    cout << checkInclusion("ab", "eidbaooo") << "\n"; // 1 (true — "ba")
    cout << checkInclusion("ab", "eidboaoo") << "\n"; // 0 (false)
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars