Permutation in String

MediumSliding Windowsliding window

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given two strings s1 and s2, determine whether s2 contains at least one substring that is a permutation of s1. A permutation of s1 is any rearrangement of its characters using each character the exact same number of times. In other words, return true if some contiguous window of s2 has precisely the same multiset of characters as s1, and false otherwise. Both strings consist only of lowercase English letters. Note that the matching window in s2 must have the same length as s1, since a permutation uses every character of s1 exactly once.

Examples

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
The window "ba" in `s2` is a permutation of "ab".
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
No contiguous window of length 2 in `s2` is a rearrangement of "ab".
Input: s1 = "adc", s2 = "dcda"
Output: true
The window "dcd" is not a match, but "cda" (positions 1..3) rearranges to "adc".

Constraints

  • 1 <= s1.length, s2.length <= 10^4
  • `s1` and `s2` consist of lowercase English letters only.
  • If `s1.length > s2.length`, the answer is always `false`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More sliding window problems