Permutation in String
The key idea
A permutation of
s1 is any substring of s2 with the exact same character counts as s1. Slide a fixed-size window of length len(s1) across s2 and compare letter frequencies; a match means an anagram is present.Problem
You are 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.
A permutation is a rearrangement of all the characters of a string, so you must match the exact character counts of s1 within a contiguous slice of s2.
Constraints
1 <= s1.length, s2.length <= 10^4s1ands2consist of lowercase English letters.
Examples
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Sliding Window problems
- Find All Anagrams in a StringMEDIUM
- Longest Continuous Increasing SubsequenceEASY
- Longest Repeating Character ReplacementMEDIUM
- Longest Subarray of 1's After Deleting One ElementMEDIUM
- Longest Substring Without Repeating CharactersMEDIUM
- Max Consecutive Ones IIIMEDIUM
- Maximum Average Subarray IEASY
- Maximum Number of Vowels in a Substring of Given LengthMEDIUM
- Minimum Size Subarray SumMEDIUM
- Minimum Window SubstringHARD
- Sliding Window MaximumHARD
- Substring with Concatenation of All WordsHARD