Given two strings s1 and s2, return true if some rearrangement (permutation) of s1 appears as a contiguous substring of s2, and false otherwise.
Example 1
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
s2 contains "ba", which is a permutation of "ab".Example 2
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints
- 1 <= s1.length, s2.length <= 10^4
- Both strings contain only lowercase English letters
Hints
Frequently asked at: Microsoft, Amazon, Meta, Oracle
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Generating all permutations of s1 is factorial time. A permutation is just the same multiset of letters, so we only need to know whether some window of s2 of length len(s1) has the same letter counts as s1. Sliding the window by one changes just two counts, and comparing two arrays of 26 counts is constant time, so the whole scan is linear.
Algorithm
- If
len(s1) > len(s2), returnfalse. - Count letters of
s1intoneed, and of the firstlen(s1)letters ofs2intowindow. - If they match, return
true. - Slide: add
s2[i], removes2[i - len(s1)], and compare again. - Return
falseif no window matched.
Time:
O(26 * n), which is O(n)Space: O(1), two arrays of 26Interview tip: You can avoid the 26-step comparison by tracking how many of the 26 letters currently have equal counts and updating that number as letters enter and leave. Interviewers like this refinement.
class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: m, n = len(s1), len(s2) if m > n: return False need = [0] * 26 window = [0] * 26 for i in range(m): need[ord(s1[i]) - 97] += 1 window[ord(s2[i]) - 97] += 1 if need == window: return True for i in range(m, n): window[ord(s2[i]) - 97] += 1 # letter entering window[ord(s2[i - m]) - 97] -= 1 # letter leaving if need == window: return True return FalseCtrl + Enter runs the examples