Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Permutation in String

LeetCode #567Medium
Fixed-size window + frequency match

Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a contiguous substring (a window of length |s1| whose character counts match s1).

Asked atAmazonMicrosoftBloomberg
step 1 / 16
e
i
d
b
a
o
o
o
[0][1][2][3][4][5][6][7]
Fixed-size window · frequency match
▸
1given s1, s2;  k ← |s1|
2target ← char counts of s1
3build first window s2[0..k − 1]
4    count each char into window
5if window counts == target: return true
6for right ← k to |s2| − 1:
7    remove s2[right − k]; add s2[right]
8return false
state
  • s1"ab"
  • s2"eidbaooo"
  • k2

line 1Does s2 contain a PERMUTATION of s1 = "ab" as a contiguous substring? A permutation is any window of length |s1| = 2 whose letter counts equal s1's.