Data structures and algorithms
## Permutation in String

###### Example 1:

###### Example 2:

###### Constraints:

##### Solution:

###### Time/Space Complexity:

###### Explanation:

comments powered by Disqus

**Permutation in String:**
Given two strings `s1`

and `s2`

, return * true if s2 contains a permutation of s1, or false otherwise*.

In other words, return `true`

if one of `s1`

’s permutations is the substring of `s2`

.

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

```
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
```

`1 <= s1.length, s2.length <= 10^4`

`s1`

and`s2`

consist of lowercase English letters.

Try this Problem on your own or check similar problems:

```
class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] freqMap = new int[26];
int l1 = s1.length(), l2 = s2.length();
if(l1 > l2) return false;
for(int i = 0; i < l1; ++i){
freqMap[s1.charAt(i) - 'a']++;
freqMap[s2.charAt(i) - 'a']--;
}
if(found(freqMap)) return true;
for(int i = l1; i < l2; ++i){
freqMap[s2.charAt(i) - 'a']--;
freqMap[s2.charAt(i-l1) - 'a']++;
if(found(freqMap)) return true;
}
return false;
}
private boolean found(int[] arr){
for(int i: arr){
if(i != 0) return false;
}
return true;
}
}
```

- Time Complexity:
*O(l2)*where`l2`

is the length of longer string - Space Complexity:
*O(1)*

We iterate over the shorter string (the one that we’re trying to find permutation for in the longer string), and for each character we increment the occurrence if it’s present in the shorter string or decrement if it’s present in the longer one. In other words, we’re keeping a window size of length `l1`

(length of the shorter string). If we find a permutation all element’s frequencies should be `0`

since we decrement and increment the same number of times. We iterate over the longer string while keeping the window size of `l1`

, each time decrementing the number of occurrences for the character that’s currently the start of our window `i-l1`

since we’re throwing it away and shifting the window to the right and incrementing the character we found after we shifted one character to right (our new end of the window). Each time we check if we have the same number of characters in the window of the longer string and the whole shorter one. We use `s1.charAt(i) - 'a'`

to map lowercase letters to range `0..25`

(since by the problem statement we only have lowercase letters in both of the input strings).

Don’t settle for anything less than the crown. Join our newsletter and become the King of Interviews! **Click here** to join now and get the latest updates.