Permutation in String ​
Permutation in String — LeetCode
Return true if s2 contains a permutation of s1 as a substring.
Approach ​
Two solutions: $O(26n)$: Keep two 26-element lists. Count first strings count. Start window at (0,0). Add count of s2[r] in it's count. If r-l+1 > s1.Length, move l++. When r-l+1 == s1.Length, compare both arrays and return true if it matches.
$O(n)$: Keep a matches variable. For the length of s1, count the characters of both s1 and s2 in one-go. For 26 elements, set matches += 1 if countS1[i] == countS2[i]. Then, start r at s1.Length. Check if matches == 26, then return true. Otherwise, increase or decrease (countS1[character] == countS2[character] - 1, we overshoot by one) the matches variable. Move the l variable too, and increase or decrease (countS1[character] == countS2[character] + 1, we undershot the character) the matches variable.
Then even after exiting loop, return whether matches == 26.
Remarks ​
I came up with the first solution.
The whole trick of the second solution is to know how to increment or decrement the count.