Permutation in String
Medium · Arrays & Hashing · Hash Table · Two Pointers · String · Sliding Window
Problem
Given two strings s1 and s2, return true if some permutation of s1 appears as a contiguous substring of s2, and false otherwise.
Put another way: does s2 contain a window of length len(s1) whose letter counts match those of s1 exactly?
Examples
Input: s1 = "tac", s2 = "xxcatyy" Output: true
"cat" at index 2 is a permutation of "tac".
Input: s1 = "ab", s2 = "axxb" Output: false
The a and the b are never next to each other.
Input: s1 = "aab", s2 = "baba" Output: true
"aba" has two a’s and one b, like "aab".
Constraints
- 1 <= len(s1), len(s2) <= 10^4
- s1 and s2 consist of lowercase English letters
Approaches
- Baseline: sort every window — time O(n · m log m), space O(m)
Follow-up
How would you list every start index instead of stopping at the first? Keep sliding and record each window with matches == 26 (see the use case “Every place an anagram starts”). If the alphabet were all of Unicode, swap the 26-slot arrays for dictionaries and track matches over the letters of s1 only.
Related problems
Start free on Cariara · Coding problems · System design studio
