Permutation in String
Problem
s1 and s2, decide whether
some rearrangement of s1 appears as a contiguous substring of
s2. Return true if it does, otherwise false.s1="ab", s2="eidbaooo"Outputtrue ("ba")s1="ab", s2="eidboaoo"Outputfalse1 ≤ |s1|, |s2| ≤ 104 · lowercase English letters only
Try it yourself
class Solution {
public boolean checkInclusion(String s1, String s2) {
}
}
s1 is just a window of length
|s1| with the same letter counts. Slide that window over
s2 and track how many of the 26 letters currently have matching counts.Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.
Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.
Open the Sliding Window guide →Approaches
Brute ForceGenerate All Permutations
O(n! · n · m)Space O(n2)Recursively build every ordering of s1
(n = |s1|, m = |s2|) and test each with
s2.contains(...). Stop at the first hit.
public boolean checkInclusion(String s1, String s2) { return permute("", s1, s2); } private boolean permute(String prefix, String rest, String s2) { if (rest.isEmpty()) return s2.contains(prefix); for (int i = 0; i < rest.length(); i++) { String next = rest.substring(0, i) + rest.substring(i + 1); if (permute(prefix + rest.charAt(i), next, s2)) return true; } return false; }
Factorial blow-up — already 3.6 million orderings at n = 10.
BetterSort Every Window
O(m · n log n)Space O(n)Two strings are permutations of each other iff their sorted forms match.
Sort s1 once, then sort each length-n substring of
s2 and compare.
public boolean checkInclusion(String s1, String s2) { char[] target = s1.toCharArray(); Arrays.sort(target); for (int i = 0; i + s1.length() <= s2.length(); i++) { char[] win = s2.substring(i, i + s1.length()).toCharArray(); Arrays.sort(win); if (Arrays.equals(win, target)) return true; } return false; }
Polynomial, but re-sorts heavily overlapping windows.
OptimalSliding Window + Matched-Letters Count
O(n + m)Space O(1)diff[c] = count of c in s1 minus
count in the window; zeros = letters with diff == 0.
Each slide touches two letters, and update adjusts
zeros in O(1). zeros == 26 means the window is a
permutation.
public boolean checkInclusion(String s1, String s2) { int n = s1.length(), m = s2.length(); if (n > m) return false; int[] diff = new int[26]; // s1 count minus window count for (int i = 0; i < n; i++) { diff[s1.charAt(i) - 'a']++; diff[s2.charAt(i) - 'a']--; } int zeros = 0; for (int d : diff) if (d == 0) zeros++; for (int i = n; i < m; i++) { if (zeros == 26) return true; zeros += update(diff, s2.charAt(i) - 'a', -1); // enters window zeros += update(diff, s2.charAt(i - n) - 'a', 1); // leaves window } return zeros == 26; } private int update(int[] diff, int c, int delta) { int before = diff[c] == 0 ? 1 : 0; diff[c] += delta; return (diff[c] == 0 ? 1 : 0) - before; }
Dry runs1="ab", s2="eidbaooo"
- initewiwdbaoooa,b,e,i off → zeros=22
- i=2eiwdwbaooo+d -e → zeros=22
- i=3eidwbwaooo+b -i → zeros=24
- i=4eidbwawooo+a -d → zeros=26 ✔
Linear and constant memory; no 26-wide comparison per step.
true at the first
match instead of collecting indices.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Generate All Permutations | O(n! · n · m) | O(n2) |
| Better | Sort Every Window | O(m · n log n) | O(n) |
| Optimal | Sliding Window + Matched-Letters Count | O(n + m) | O(1) |
- Forgetting the final
zeros == 26check after the loop — misses the last window. - Not returning
falseearly when|s1| > |s2|(index out of bounds). - Checking
s2.contains(s1)only — order of letters doesn't matter here.
- Restate as “does any length-|s1| window have the same letter counts?”
- Mention the brute force only to motivate counting instead of enumerating.
- Two-array compare (O(26·m)) is fine to code first; then refine to the counter.