Permutation In String

Asked byMicrosoftAppleYandexOracleAmazonGoogle

Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a contiguous substring — that is, one of s1's permutations is a substring of s2.

Examples

Example 1

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

Output:true

s2 contains "ba", a permutation of s1.

Example 2

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

Output:false

Constraints

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

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Sliding Window pattern

A window — a contiguous subarray or substring — expands and shrinks as it moves across the input, so you track a running condition instead of recomputing it from scratch for every possible window.

Look for this pattern when

The problem asks for the longest/shortest/best contiguous subarray or substring meeting a condition.
Brute force would recompute a sum or count for every possible window — a sign that work can be shared between overlapping ranges.

Read the full Sliding Window guide →

Video walkthroughs

Original problem on LeetCode ↗