18.Permutation in String

MediumSliding Window · 4/6

Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring, otherwise return false.

In other words, is there a contiguous block of s2 of length s1.length() that uses exactly the same letters, with the same counts, as s1?

Examples

Input:  s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains "ba" (indices 3–4), which is a permutation of "ab".

Input:  s1 = "ab", s2 = "eidboaoo"
Output: false
Explanation: No length-2 window of s2 contains exactly one 'a' and one 'b'.

Constraints

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

💡 Key Insight

Two strings are permutations of each other iff their letter-frequency vectors are equal. Since the target window has a fixed length m = s1.length(), slide a window of size m across s2: adding one character and removing one changes only two counts. Track how many of the 26 letters currently have matching counts — when all 26 match, we found a permutation.

Brute Force (Sort Every Window)

TimeO(n · m log m)SpaceO(m)

Intuition

A window is a permutation of s1 iff sorting both gives the same string. So sort s1 once, then sort every length-m window of s2 and compare.

Algorithm

If m > n, return false.
Sort s1 into target.
For each start i from 0 to n - m: sort s2[i..i+m-1]; if it equals target, return true.
Return false.

Visualization

s1 = "ab" → sorted "ab"
s2 = "eidbaooo"

"ei"→"ei" ✗  "id"→"di" ✗  "db"→"bd" ✗  "ba"→"ab" ✓ → true

Code

java

import java.util.Arrays;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) {
            return false;
        }
        char[] target = s1.toCharArray();
        Arrays.sort(target);
        for (int i = 0; i + m <= n; i++) {
            char[] window = s2.substring(i, i + m).toCharArray();
            Arrays.sort(window); // permutations become identical once sorted
            if (Arrays.equals(window, target)) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(n · m log m) — n - m + 1 windows, each sorted in O(m log m).
Space: O(m) — the copy of each window.

Sliding Window + Compare Count Arrays

TimeO(26 · n)SpaceO(1)

Intuition

Sorting throws away work: neighbouring windows share m - 1 characters. Keep a 26-slot count array for the current window; moving the window right adds one character and removes one. After each move, compare the window counts with s1's counts (26 comparisons).

Algorithm

Build need[26] from s1 and have[26] from the first m characters of s2.
If need == have, return true.
For right from m to n - 1: increment have[s2[right]], decrement have[s2[right - m]]; if need == have, return true.
Return false.

Dry Run

s1 = "ab" → need: a=1 b=1
s2 = "eidbaooo"

window "ei": e=1 i=1          ✗
window "id": i=1 d=1          ✗
window "db": d=1 b=1          ✗
window "ba": b=1 a=1          ✓ → true

Code

java

import java.util.Arrays;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) {
            return false;
        }
        int[] need = new int[26];
        int[] have = new int[26];
        for (int i = 0; i < m; i++) {
            need[s1.charAt(i) - 'a']++;
            have[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(need, have)) {
            return true;
        }
        for (int right = m; right < n; right++) {
            have[s2.charAt(right) - 'a']++;      // char entering the window
            have[s2.charAt(right - m) - 'a']--;  // char leaving the window
            if (Arrays.equals(need, have)) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(26 · n) — each slide is O(1) plus a 26-element comparison.
Space: O(1) — two fixed 26-slot arrays.

Sliding Window + Matches CounterOptimal

TimeO(n)SpaceO(1)

Intuition

Instead of comparing all 26 counts every step, maintain matches = the number of letters whose count in the window equals their count in s1. A slide changes only two letters, so matches can be updated in O(1): a letter can move into agreement (+1) or out of agreement (−1). When matches == 26, the window is a permutation.

Algorithm

Build need and have for s1 and the first window; compute matches by comparing all 26 once.
For right from m to n - 1:
- If matches == 26, return true.
- Add c = s2[right]: increment have[c]; if now equal to need[c], matches++; else if it was equal just before (have[c] == need[c] + 1), matches--.
- Remove d = s2[right - m]: decrement have[d]; if now equal, matches++; else if it was equal before (have[d] == need[d] - 1), matches--.
Return matches == 26.

Dry Run

flowchart TD
    A["need: a=1, b=1<br/>window 'ei': a, b, e, i disagree<br/>matches = 22"] --> B["add 'd' (0 to 1, was equal) -1<br/>drop 'e' (1 to 0, now equal) +1<br/>window 'id': matches = 22"]
    B --> C["add 'b' (now 1 = need) +1<br/>drop 'i' (now 0 = need) +1<br/>window 'db': matches = 24"]
    C --> D["add 'a' (now 1 = need) +1<br/>drop 'd' (now 0 = need) +1<br/>window 'ba': matches = 26"]
    D --> E{"matches == 26?"}
    E -->|"yes"| F["return true"]

Code

java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) {
            return false;
        }
        int[] need = new int[26];
        int[] have = new int[26];
        for (int i = 0; i < m; i++) {
            need[s1.charAt(i) - 'a']++;
            have[s2.charAt(i) - 'a']++;
        }
        int matches = 0; // letters whose counts agree
        for (int i = 0; i < 26; i++) {
            if (need[i] == have[i]) {
                matches++;
            }
        }
        for (int right = m; right < n; right++) {
            if (matches == 26) {
                return true;
            }
            // add the incoming character
            int in = s2.charAt(right) - 'a';
            have[in]++;
            if (have[in] == need[in]) {
                matches++;
            } else if (have[in] == need[in] + 1) {
                matches--; // it was matching before this increment
            }
            // remove the outgoing character
            int out = s2.charAt(right - m) - 'a';
            have[out]--;
            if (have[out] == need[out]) {
                matches++;
            } else if (have[out] == need[out] - 1) {
                matches--; // it was matching before this decrement
            }
        }
        return matches == 26;
    }
}

Complexity

Time: O(n) — 26 work once, then O(1) per slide.
Space: O(1) — two fixed 26-slot arrays.

Complexity Comparison

Approach	Time	Space
Brute Force (sort windows)	O(n · m log m)	O(m)
Sliding Window + compare arrays	O(26 · n)	O(1)
Sliding Window + matches counter	O(n)	O(1)

Common Pitfalls

Generating all permutations of s1 — that is O(m!) and explodes immediately.
Forgetting the m > n early exit; the initial loop would index past the end of s2.
Checking matches == 26 only inside the loop and forgetting the last window — return matches == 26 after the loop.
In the matches update, only decrementing when counts "become unequal" without checking they were equal before — that double-counts and corrupts matches.