Permutation in String — Medium Coding Interview Question

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

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

Output: true

Explanation: s2 contains "ba", a permutation of s1.

Constraints

• 1 ≤ s1.length, s2.length ≤ 10⁴
• s1 and s2 consist of lowercase English letters

Topics & Companies

Topics: strings, sliding-window, hash-map

Asked by: Amazon, Microsoft, Meta

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(1).

Practice more

• All DSA Problems
• DSA Patterns