The problem
Given strings s1 and s2, return true if some rearrangement of s1 appears in s2 as a stretch of consecutive characters, and false otherwise.
Examples
01
- Input
s1 = "ab", s2 = "eidbaooo"
- Output
true
02
- Input
s1 = "ab", s2 = "eidboaoo"
- Output
false
Constraints
- 1 ≤ s1.length, s2.length ≤ 10⁴
- Both contain only lowercase English letters.
The idea
A rearrangement of s1 has exactly the same letter counts as s1, and the same length. So slide a window of exactly s1.length across s2, and ask whether its counts match.
Keep need[c], how many more of letter c the window still needs, and missing, the total still needed. A letter entering lowers missing if it was needed; a letter leaving raises it again if it becomes needed. When missing is 0, the window is a rearrangement.
- Time
- O(n) over s2
- Space
- O(1) — 26 counters
Solution · every language run against every case
class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: n = len(s1) if n > len(s2): return False need = [0] * 26 # how many more of each letter the window still needs for c in s1: need[ord(c) - 97] += 1 missing = n # letters of s1 not yet matched by the window for r, c in enumerate(s2): if need[ord(c) - 97] > 0: missing -= 1 need[ord(c) - 97] -= 1 if r >= n: # the window is too long: drop its first letter d = ord(s2[r - n]) - 97 need[d] += 1 if need[d] > 0: missing += 1 if missing == 0: return True return False