Permutation in String

Problem in Plain English

Given strings s1 and s2, return true when some contiguous substring of s2 is a rearrangement of s1, using exactly the same multiset of characters.

Problem Statement

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

A permutation keeps the exact multiset of letters, so the task equals asking whether some window of s2 with length s1.length has identical letter counts to s1. For s1 = "ab" and s2 = "eidbaooo" the window "ba" matches, so the answer is true.

Constraints

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

Examples

Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true

The substring "ba" at indices 3 to 4 is a permutation of "ab".

Example 2

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

No length-2 window of s2 holds exactly one "a" and one "b".

Example 3

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

The required length is 3 but the text has only 2 characters, so no candidate window exists.

Example 4

Input: s1 = "aab", s2 = "aaaba"
Output: true

The first window aaa has three a letters and no b, so it fails. The next window aab at indices 1 through 3 has exactly two a letters and one b, so it succeeds; merely finding both distinct letters would not suffice.

Intuition

A permutation changes order but preserves how many copies of each letter exist. A window is a contiguous group of characters; any candidate here must have exactly m = s1.length characters. In Example 1, ab needs one a and one b, so ba succeeds even though the order differs. Counting letters avoids generating permutations. Neighbouring windows share all but their entering and departing characters, letting us update the counts instead of recounting them.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Check each possible start independently by rebuilding the letter counts of its length-m window. This makes the test simple, but recounts the m-1 shared letters whenever the window moves.

Step-by-Step Logic

Let m = s1.length and n = s2.length; return false if m exceeds n, otherwise count the 26 lowercase letters of s1. Example 1 needs a1,b1 with m=2 and n=8.
For every start from 0 through n-m, reset have to zero and count characters at start through start+m-1. Example 1 starts with ei, then id, then db.
Compare all 26 counts against need. Reject any window with a differing count; a missing letter and an extra letter both matter.
Return true at the first equal window: start=3 gives ba with a1,b1. If all starts fail, return false.

Why It Works

Every permutation has the same length and exactly the same multiplicity for each letter as s1. Conversely, a string with those multiplicities can be arranged into s1, so count equality is sufficient. The outer loop visits every possible length-m substring start exactly once. Returning true therefore identifies a valid permutation, and exhausting the starts proves none exists.

Dry Run

Brute Force: variable states at each step
start	inner index and have transitions (unlisted counts are 0)	First mismatch / equality	Result
setup	need: a1,b1; m=2; n=8	have reset for each start	pending
0	i=0: e0→1; i=1: i0→1	a: have0 versus need1	continue
1	i=0: i0→1; i=1: d0→1	a: have0 versus need1	continue
2	i=0: d0→1; i=1: b0→1	a: have0 versus need1	continue
3	i=0: b0→1; i=1: a0→1	all 26 counts equal	true

Complexity Analysis

Time Complexity

O(nm)

Space Complexity

O(1)

Let m=s1.length and n=s2.length. Counting the target costs O(m); each of n-m+1 valid windows costs O(m+26), including count comparison. O(nm) is a worst-case upper bound for fixed alphabet size 26. Two 26-entry arrays use constant auxiliary space; no substring or sort is allocated. If m exceeds n, the guard returns in O(1).

Code

Solution.java

1class Solution {2    public boolean checkInclusion(String s1, String s2) {3        if (s1.length() > s2.length()) {4            return false;5        }6        int[] need = new int[26];7        for (int i = 0; i < s1.length(); i++) {8            need[s1.charAt(i) - 'a']++;9        }10        for (int start = 0; start + s1.length() <= s2.length(); start++) {11            int[] have = new int[26];12            for (int i = 0; i < s1.length(); i++) {13                have[s2.charAt(start + i) - 'a']++;14            }15            boolean same = true;16            for (int i = 0; i < 26; i++) {17                if (have[i] != need[i]) {18                    same = false;19                    break;20                }21            }22            if (same) {23                return true;24            }25        }26        return false;27    }28}

Hints

Hint 1

Two strings are permutations of each other exactly when their letter counts agree on all 26 letters.

Hint 2

Any matching substring must sit in one window of length s1.length, so only those fixed-size windows need checking.

Hint 3

Slide that window one step at a time: each step adds one letter on the right and drops one on the left, so the counts update in constant time.

Edge Cases

s1 is longer than s2: no window of the required size exists, so the answer is false.
Single equal letters such as s1 = "a" and s2 = "a": the first window already matches and the answer is true.
s2 is all one repeated letter, such as s1 = "ab" with s2 = "aaaa": counts never align and the answer is false.
Equal-length strings have only the initial window; the final matches check handles both success and failure.
Repeated multiplicities matter: aab does not match abb despite having the same distinct letters.
The last window may be the only match: ab inside oooba must return true.
When the entering and departing letters are equal, perform both updates; the final count and matches value must return to their previous state.

Common Mistakes and Interview Tips

Comparing distinct-letter sets loses multiplicities: aab and abb have the same set but are not permutations.
Updating matches every time a count changes, rather than only when equality is created or destroyed, corrupts the invariant.
Checking only at the start of slide iterations misses the final window; compare matches after the loop too.
Using a variable-size window answers a different question: every candidate must have exactly s1.length characters.
Interview tip: explain why absent letters with counts zero still contribute to the 26 matches, then trace an add and a drop separately.

Key Takeaway

For anagram or permutation checks inside a string, hold one fixed-size window and update its frequency counts incrementally instead of rebuilding them.