Permutation in String

Medium#567fixed size

You get two strings, s1 and s2. Find out whether s2 contains s1 with its letters in some order, as one piece of letters in a row. Our example: s1 = "loot", s2 = "tollotool" — yes: "loto" at index 3.

567 Permutation in StringWalkthrough · 1×

Example: s1 = "loot", s2 = "tollotool". Under s2 is need: how many of each letter the window still lacks. 0 is faded, below 0 means too many.

0t1o2l3l4o5t6o7o8lneed—s1 = "loot"
not reached yet, still lackingwindowletter coming inletter going out, too manyleft the window, count 0a permutation of s1

s1 has 4 letters: the window is 4 letters long

01/34
restart · back · play · step
Speed
1function checkInclusion(s1, s2):
2 m = len(s1)
3 need = count of each letter in s1 // missing keys: 0
4 for right from 0 to len(s2) - 1:
5 need[s2[right]] = need[s2[right]] - 1
6 if right >= m:
7 need[s2[right - m]] = need[s2[right - m]] + 1
8 if every count in need is 0:
9 return true
10 return false
state
m
4
need
–
right
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A permutation of s1 is exactly as long as s1, so only windows of that length can be one, and the window slides one letter at a time over every place it could start.
  2. need starts as the counts of s1; a letter coming in takes one away, a letter leaving gives one back. Every count is 0 exactly when the window has the same letters as s1, each the same number of times.
  3. Having the right letters is not enough: "toll" has l, o and t, but one "l" too many and one "o" short. That is why the map keeps counts, not a set.

Complexity

Time O(26 · n), where n is the length of s2: each letter comes in and leaves once, and checking need looks at most at 26 counts. Memory O(1): at most 26 counts.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.