How do you approach Permutation in String?

Two strings are permutations of each other exactly when their letter frequency counts match.

What is the time complexity of Permutation in String?

Time complexity: O(n) - one pass over s2 with O(1) work per slide. Space complexity: O(26) = O(1) - two fixed-size frequency tables.

What are common mistakes on Permutation in String?

Shrinking with if instead of while - one removal is often not enough to restore the invariant. Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove. Never recording the answer for a window that ends at the last index.

gitGood.dev

← Back to problems

Permutation in String

MediumAlgorithms

Description

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`'s permutations is a **substring** of `s2`.

Example 1

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

Output: true

Explanation: s2 contains one permutation of s1 ("ba").

Example 2

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

Output: false

Example 3

Input: s1 = "adc", s2 = "dcda"

Output: true

Explanation: The substring "cda" is a permutation of "adc".

Constraints

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

Permutation in String: approach, complexity and pitfalls

A medium sliding window problem, graded against 7 test cases (4 of them hidden).

The pattern: Sliding Window

A moving window over a contiguous run, expanding and contracting to hold an invariant.

Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."

More Sliding Windowproblems →

If you are stuck

Show the 3-step hint ladder

Two strings are permutations of each other exactly when their letter frequency counts match.
Slide a window of length s1.length across s2 and compare frequency counts.
Instead of re-comparing 26 counts every step, track how many of the 26 letters currently match and update that tally as one character enters and one leaves the window.

The optimal approach

Show the approach: Fixed-Size Sliding Window over Frequency Counts

A permutation of `s1` is any window of length `s1.length` in `s2` with identical letter frequencies. Build the frequency table of `s1` and of the first window of `s2`, and count how many of the 26 letters already match. Then slide the window one character at a time: each slide changes the count of exactly two letters (the one entering, the one leaving), so the matches tally can be updated in O(1). The answer is true the moment all 26 letters match.

Time: O(n) - one pass over s2 with O(1) work per slide
Space: O(26) = O(1) - two fixed-size frequency tables

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Sliding Window mistakes

These apply to the pattern as a whole, not just this problem.

Shrinking with `if` instead of `while` - one removal is often not enough to restore the invariant.
Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove.
Never recording the answer for a window that ends at the last index.

← Back to problems

Permutation in String

MediumAlgorithms

Description

Example 1

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

Output: true

Explanation: s2 contains one permutation of s1 ("ba").

Example 2

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

Output: false

Example 3

Input: s1 = "adc", s2 = "dcda"

Output: true

Explanation: The substring "cda" is a permutation of "adc".

Constraints

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

Permutation in String: approach, complexity and pitfalls

A medium sliding window problem, graded against 7 test cases (4 of them hidden).

The pattern: Sliding Window

A moving window over a contiguous run, expanding and contracting to hold an invariant.

Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."

More Sliding Windowproblems →

If you are stuck

Show the 3-step hint ladder

Two strings are permutations of each other exactly when their letter frequency counts match.
Slide a window of length s1.length across s2 and compare frequency counts.
Instead of re-comparing 26 counts every step, track how many of the 26 letters currently match and update that tally as one character enters and one leaves the window.

The optimal approach

Show the approach: Fixed-Size Sliding Window over Frequency Counts

Time: O(n) - one pass over s2 with O(1) work per slide
Space: O(26) = O(1) - two fixed-size frequency tables

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Sliding Window mistakes

These apply to the pattern as a whole, not just this problem.

Shrinking with `if` instead of `while` - one removal is often not enough to restore the invariant.
Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove.
Never recording the answer for a window that ends at the last index.