# [Permutation in String](https://leetcode.com/problems/permutation-in-string/submissions/840226479/)
###### tags: `Leetcode`, `Medium`, `Sliding Window`

## Approach
**Example: s1="ab", s2="eidbaooo"**
1. We will use the Sliding Window method with HashMap to solve this problem
2. *Base Condition:*

if len(s1) > len(s2): return False

3. Initialize two hashmaps `s1_count` and `s2_count`. These will have every letter of the alphabet as the key and a default value of 0
4. For the length of the string `s1`, increment the value of each letter by one in both the hashmaps i.e. *the first two letters of s2 will have their values incremented in `s2_count`*
5. Initialize `matches = 0` to keep track of the total matches between both the hashmaps
6. Iterate through `a to z` and for every matching value in both the hashmaps, increment `matches` by one
7. Initialize a pointer `left = 0` and start another pointer `right` which will range from `len(s1) to len(s2)`. This is because we have already taken the first `len(s1)` letters of `s2` and incremented the values in the hashmaps.
1. *Base Condition (for loop)*: This means that every pair of `s1_count` matches with that of `s2_count`. It is 26 because there are 26 letters in the alphabet.

        if matches == 26: return True

2. Increment the value of `s2_count` of the letter that `right` points to and check if that value matches in both the hashmaps. If they match, increment match by one. In case incrementing the value has now caused the values to differ in both the hashmaps, decrement match count by one.
3. Decrement the value of `s2_count` of the letter that `left` points to and check if that value matches in both the hashmaps. If they match, increment the value of match by one. In case, decrementing the value has caused the values to differ in both the hashmaps, decrement match count by one.
4. Increment `left` by one
8. `return matches == 26`. This is because it is possible that after the last iteration of the for loop matches can become equal to 26.

## Asymptotic Analysis
### Time Complexity: **O(N1 + 26.(N2 - N1))**
### Space Complexity: **O(1)**

## Code

"""
Approach: Sliding Window
Time Complexity: O(l1 + 26*(l2 - l1)), where l1, l2 = length of s1, length of s2
Space Complexity: O(1), because the map always stores exactly 26 elements
"""
import sys

class PermutationInString:
    # eg: s1='ab' s2='eidbaooo'
    def _check_inclusion(self, s1: str, s2: str) -> bool:
        # return false if size of s1 is smaller than size of s2
        if len(s1) > len(s2): return False
        # initialize two dictionaries corresponding to s1 and s2.
        # set every letter of the alphabet to have initial count as 0
        s1_count, s2_count = {}, {}
        for index in range(ord('a'), ord('z') + 1):
            s1_count.setdefault(chr(index), 0)
            s2_count.setdefault(chr(index), 0)
        # for the length of s1 set the count of every letter in s1_count and 
        # those many letters in s2_count
        for index in range(len(s1)):
            s1_letter, s2_letter = s1[index], s2[index]
            s1_count[s1_letter] += 1
            s2_count[s2_letter] += 1
        # initialize matches to keep track of match count
        # set matches to 0 initially
        # for every matching value of key in s1_count and s2_count,
        # increment matches
        matches = 0
        for index in range(ord('a'), ord('z') + 1):
            matches += 1 if s1_count[chr(index)] == s2_count[chr(index)] else 0
        # start from the next letter after len(s1) letters in the string s2
        left = 0
        for right in range(len(s1), len(s2)):
            # if match count is 26 then return true
            if matches == 26: return True
            # for every right index position, add 1 to its count dict
            letter = s2[right]
            s2_count[letter] += 1
            # if the count of that letter matches that of s1 then increment
            # matches else if the the count of that letter was matching with
            # s1_count and has now increased after incrementing in s2_count,
            # then decrement matches
            if s2_count[letter] == s1_count[letter]:
                matches += 1
            elif s1_count[letter] + 1 == s2_count[letter]:
                matches -= 1
            # move left pointer to the next index position and check for match
            # count in the same way as done above
            letter = s2[left]
            s2_count[letter] -= 1
            if s2_count[letter] == s1_count[letter]:
                matches += 1
            elif s1_count[letter] - 1 == s2_count[letter]:
                matches -= 1
            left += 1
        return matches == 26


    def process(self, str1: str, str2: str):
        print(f"\nOutput >> {self._check_inclusion(str1, str2)}\n")

if __name__ == "__main__":
    str1 = input("Enter s1: ")
    str2 = input("Enter str2: ")
    PermutationInString().process(str1, str2)