mafeshsho8lmafeshsho8l
Get Started
All coding questions

Permutation in String

medium
NeetCode 150stringssliding-windowhashing

Problem

Given two strings, decide whether the second contains any contiguous substring that is a permutation of the first. Return true if such a window exists.

Examples

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
"ba" is a permutation of "ab".
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
No window matches the letter counts of "ab".

Constraints

  • • 1 <= s1.length, s2.length <= 10^4
  • • Lowercase English letters only
Hints(tap to reveal)
  • 1. A fixed-size window has the length of the pattern.
  • 2. Compare frequency counts rather than orderings.
Optimal approach(spoiler)
  1. Build the target frequency count from the first string.
  2. Slide a window of that exact length across the second string.
  3. Maintain the window's running frequency count incrementally.
  4. Return true whenever the window count matches the target.
  5. O(n) time, O(1) space for a fixed alphabet.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor