> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/sliding-window/permutation-in-string.md).

# Permutation in String

## Problem

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.

{% hint style="info" %}
For example:

```
Input: String="oidbcaf", Pattern="abc"
Output: True
Explanation: The string contains "bca" which
is a permutation of the given pattern.
```

```
Input: String="odicf", Pattern="dc"
Output: False
Explanation: No permutation of the pattern 
is present in the given string as a substring.
```

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

{% endhint %}

### Thought Process

* We can use a **HashMap** to remember the frequencies of all characters in the given pattern. Our goal will be to match all the characters from this **HashMap** with a sliding window in the given string. 

* We have a static window size of the length of the pattern

## Solution

```
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        char_freq = {}
        start = 0
        match = 0
        
        for i in range(len(s1)):
            if s1[i] not in char_freq:
                char_freq[s1[i]] = 0
            char_freq[s1[i]]+=1
            
            
        for end in range(len(s2)):
            letter = s2[end]
            # decrement the frequency of matched character
            if letter in char_freq:
                char_freq[letter]-=1
                if char_freq[letter] == 0: 
                    match+=1
            
            if len(char_freq) == match:
                return True
            
            if end >= len(s1)-1:
                char = s2[start]
                if char in char_freq:
                    if char_freq[char] == 0:
                        match-=1
                    char_freq[char]+=1
                start+=1
        return False
                        
```

### Follow Up: Can you find all Anagrams in the String

```
def find_string_anagrams(str, pattern):
  result_indexes = []
  charFreq = {}
  match = 0
  start = 0

  for i in range(len(pattern)):
    if pattern[i] not in charFreq:
      charFreq[pattern[i]] = 0
    charFreq[pattern[i]]+=1

  for end in range(len(str)):
    letter = str[end]

    if letter in charFreq:
      charFreq[letter]-=1
      if charFreq[letter] == 0:
        match+=1
    
    if match == len(charFreq):
      result_indexes.append(start)

    if end >= len(pattern) - 1:
      char = str[start]
      if char in charFreq:
        if charFreq[char] == 0:
          match-=1
          charFreq[char]+=1
      start+=1


  return result_indexes


```

## Key Points

* Using a frequency hash map to compare pattern's character frequency with the characters in our sliding window

* We are moving our window in the size of our pattern so that the current window size (and the characters within it) can always be compared to our pattern

* When char\_freq\[letter] hits 0, that means we have found all occurences of that letter in our string

* Using a static window

* Before we add the next letter, we shrink our window first

* We are comparing the len(hashMap) because haspMap has all the count of characters

## Time Complexity

* **Time:** $$O(N+M)$$ where ‘N’ and ‘M’ are the number of characters in the input string and the pattern, respectively.

* **Space:** $$O(M)$$ since in the worst case, the whole pattern can have distinct characters that will go into the HashMap.