## DEV Community

Aroup Goldar Dhruba

Posted on

# LeetCode: Permutation in String

### Problem Statement

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

``````Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").
``````

Example 2:

``````Input:s1= "ab" s2 = "eidboaoo"
Output: False
``````

Note:

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

### Solution Thought Process

As we have to find a permutation of string `s1` , let's say that the length of `s1` is `k`. We can say that we have to check every `k` length subarray starting from 0. Let's say that length of `s2` is L.

Let's store all the frequencies in an `int remainingFrequency[26]={0}`. Whenever we found an element we decrease it's remaining frequency.

The algorithm boils down to these step:

• Check `[0,k-1]` - this k length window, check if all the entries in the remaining frequency is 0

• Check `[1,k]` - this k length window, check if all the entries in the remaining frequency is 0

• Check `[2,k+1]` - this k length window, check if all the entries in the remaining frequency is 0

.............................................................

.............................................................

• Check `[windowStart+k-1,L-1]` - this k length window, check if all the entries in the remaining frequency is 0

If the frequencies are 0, then we can say that the permutation exists. For each window we have to consider the `26` values to determine if the window is an permutation.

So one thing we get hunch from here, this can be easily done in O(n) instead on any quadric time complexity.

Why?

When rolling over the next window, we can remove the left most element, and just add one right side element and change the remaining frequencies. This is called the sliding window technique.

### Solution

``````class Solution {
private:
int remainingFrequency[26]={0};
bool checkFrequency(int *frequency)
{
for(int i=0;i<26;i++)
{
if(frequency[i]!=0)
{
return false;
}
}
return true;
}
public:
bool checkInclusion(string s1, string s2) {
int k=s1.size();
for(int i=0;i<k;i++)
{
remainingFrequency[s1[i]-'a']++;
}
int windowStart=0;
for(int windowEnd=0;windowStart+k-1<s2.size();windowEnd++)
{
remainingFrequency[s2[windowEnd]-'a']--;
if(windowEnd>=k-1)
{
if(checkFrequency(remainingFrequency))
{
return true;
}
remainingFrequency[s2[windowStart]-'a']++;
windowStart++;
}
}
return false;
}
};
``````

### Complexity

Time Complexity: O(n)

Space Complexity: O(1)