Permutation in String: definition
A permutation rearranges letters without changing their counts. This problem asks whether such a rearrangement appears as one contiguous part of another string.
Task example: Permutation in String
Given lowercase English strings s1 and s2, return True if some contiguous part of s2 contains exactly the letters of s1, including repeated counts. Otherwise return False. The matching part must have length len(s1).
The substring ba has one a and one b, so it matches ab. In eidboaoo the letters occur separately; a subsequence is not enough.
Brute force: video explanation
s1 = "ab", s2 = "eidbaooo" → True
Prefer reading? Follow the steps below.
- Let m = len(s1). Count the required letters once in need. Try every start that has room for m characters.
- For each start, create a fresh window Counter and count its m letters using indices. Compare the whole frequency table with need.
- The candidates ei, id, and db fail. The candidate ba matches, so return True immediately. If every candidate fails, return False.
Time complexity · O(nm)
For m = len(s1) and n = len(s2), when m ≤ n, building need takes O(m), and n - m + 1 candidates each require O(m) counting. Total: O(m + (n - m + 1)m), bounded by O(nm). If m > n, this version only builds need: O(m).
Space complexity · O(1)
Each Counter has at most 26 lowercase English letters. Extra space is O(1) for this fixed alphabet. No substring copies are created.
Sliding window: video explanation
s1 = "ab", s2 = "eidbaooo" → True
Prefer reading? Follow the steps below.
- Count s1 and the first m letters of s2. If m > len(s2), return False. Check the first window before sliding.
- For each slide, add s2[right] and subtract s2[right - m]. Compare only after both updates, when the window again has exactly m letters.
- In eidbaooo, slide ei → id → db → ba. The last window matches need, so return True. Counter equality treats missing letters as zero counts in Python 3.10 and later.
The optimal approach reuses the previous window instead of recounting m letters. Only one letter enters and one leaves. Counts preserve repeated letters, so aab can match aba but cannot match abb.
Time complexity · O(m + n)
Time is O(m + n) for the fixed 26-letter alphabet. Build the counts once, then perform at most n - m slides. Each comparison checks at most 26 counts. If m > n, the early return takes O(1).
Space complexity · O(1)
Each Counter has at most 26 lowercase English letters. Extra space is O(1) for this fixed alphabet. No substring copies are created.