Permutation in String
You can check if s2
contains a permutation of s1
by using a sliding window approach combined with the concept of frequency counts.
Here’s the code:


Explanation
Create Counters: You create counters for
s1
and a window of characters ins2
.s1_count
holds the frequency of each character ins1
, andwindow_count
will keep track of the characters in the current window ofs2
.Sliding Window: You iterate through
s2
and at each step, add the current character to the window (increasing its count inwindow_count
).Adjust Window Size: If the window size becomes greater than the length of
s1
, you remove the leftmost character from the window.Check Permutation: If at any step the
window_count
matchess1_count
, that means the current window ins2
is a permutation ofs1
, and you returnTrue
.Final Result: If no permutation is found, you return
False
.
Insights
 Sliding Window: The use of a sliding window of the same length as
s1
ensures that you only consider substrings ofs2
that could possibly be permutations ofs1
.  Time Complexity: The time complexity of this solution is (O(n)), where (n) is the length of
s2
, as you iterate throughs2
once.  Space Complexity: The space complexity is (O(1)) since the counters will hold at most 26 characters (all lowercase English letters).
Define the Terms Permutation: One of several possible variations, in which a set or number of things can be ordered or arranged.
abc cab cba …
Define the Interface Input: string s1, string s2 Output: boolean
Analyze the Input and Output
Identify the Invariants We cannot change the order in which the characters appear in string s1.
Identify the constraints
 The input strings only contain lower case letters.
 The length of both given strings is in range [1, 10,000].
We cannot create substrings, it will be inefficient.
Search the Problem Space
Classify the Problem
Analyze the Examples
Solve the Problem by Hand
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
 Take every substring of length of s1 in s2 Sort the substring Check if it is equal to the sorted version of s1.
Time: O(N * M Log N) + O(N) Space: O(1)
Analyze Time and Space Complexity
Outline the Solution
Keep the frequency of all the characters in s1 array frequency counter
Scan through the string s2 and check if the substring is consisting of the same frequency as you have for s1 frequency counter.
We can think of the substring size in s2 as a fixed window size equal to s1 length.
Keep moving this window from left to right looking for the permutation using the frequency counter.
Sort both strings
“ab” s2 = “eidbaooo” becomes ‘ab’, “abdeiooo” This approach will violate the invariant and transform the problem to a different problem. We will solve the wrong problem.


title: Permutation in String excerpt: Code for Permutation in String and Find All Anagrams in a String problems. tags: arrayfrequencycounter asciicode
Solution
Comments explaining the code that I found online.


With a few modifications, we can make the code work to solve Find All Anagrams in a String problem:


Building Block
 Array as Frequency Counter