DSA Tracker

Visualize

Permutation in String

Fixed-width sliding window over letter counts

time O(n)space O(1)

A permutation of s1 is any rearrangement of its letters, so a matching substring must be exactly as long as s1 and use exactly the same letters, however they are ordered. That means the answer never depends on position inside the window — only on how many of each letter it holds. Count the letters of s1 once, count the first window of that width in s2, then slide the window one step at a time: each step adds the letter entering on the right and removes the one leaving on the left, so re-counting from scratch is never needed and each window costs a constant amount of work.

Details

Animated on: s1 = "abc", s2 = "eidbaobca" — does s2 contain a permutation of s1 as a contiguous substring?

Problem:Permutation in StringMedium

Pattern:Sliding Window

Fixed-width sliding window over letter counts

step 1 / 8

e
[0]
i
[1]
d
[2]
b
[3]
a
[4]
o
[5]
b
[6]
c
[7]
a
[8]

Looking for any 3-letter stretch of "eidbaobca" that uses exactly the same letters as "abc". Order inside the stretch does not matter, so only the letter COUNTS have to match — that turns the search into one 3-wide window sliding right.

Pseudocode
1FUNCTION checkInclusion(s1, s2):
2  k <- LENGTH(s1)
3  need <- COUNTS(s1)
4  win <- COUNTS(s2[0 TO k - 1])
5  IF win = need:
6    RETURN TRUE
7  FOR r <- k TO LENGTH(s2) - 1:
8    win[s2[r]] <- win[s2[r]] + 1
9    win[s2[r - k]] <- win[s2[r - k]] - 1
10    IF win = need:
11      RETURN TRUE
12  RETURN FALSE

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Looking for any 3-letter stretch of "eidbaobca" that uses exactly the same letters as "abc". Order inside the stretch does not matter, so only the letter COUNTS have to match — that turns the search into one 3-wide window sliding right.
  2. First window "eid" holds 0 'a' but "abc" needs 1, so these 3 letters cannot be a rearrangement of it. Slide right.
  3. Dropping 'e' and taking in 'b' gives "idb", which holds 0 'a' against the 1 "abc" needs — still not a match, so keep sliding.
  4. Dropping 'i' and taking in 'a' gives "dba", which holds 0 'c' against the 1 "abc" needs — still not a match, so keep sliding.
  5. Dropping 'd' and taking in 'o' gives "bao", which holds 0 'c' against the 1 "abc" needs — still not a match, so keep sliding.
  6. Dropping 'b' and taking in 'b' gives "aob", which holds 0 'c' against the 1 "abc" needs — still not a match, so keep sliding.
  7. Dropping 'a' and taking in 'c' gives "obc", which holds 0 'a' against the 1 "abc" needs — still not a match, so keep sliding.
  8. 'o' left the window and 'a' entered it, and now "bca" uses exactly the letters of "abc" — a permutation starting at index 6. Return true.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Permutation in String in the editorAll Strings problemsBack to roadmap