# Permutation in String (Leetcode #567)

[**567\. Permutation in String**](https://leetcode.com/problems/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`.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* `1 <= s1.length, s2.length <= 10<sup>4</sup>`
    
* `s1` and `s2` consist of lowercase English letters.
    

### Answer:

My original approach was to use two hashmaps and a sliding window to check if s1 is a substring of s2 at any point. This will use a method similar to the question [Valid Anagram](https://hashnode.com/post/clxebdjdw00070ajycdg11df8).

But this approach leaves us in a situation where we have to check if the count of a character is equal to zero and remove it when it is. This increases the complexity and makes it harder to code.

The hint here is that s1 and s2 only contain lowercase English characters. Since we know that there can only be 26 characters we can use a list with length 26 to keep track of the count of each character.

```python
n(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        count1 = [0] * 26
        count2 = [0] * 26
        if len(s1) > len(s2):
            return False
        for i in range(len(s1)):
            count1[ord(s1[i]) - ord('a')] += 1
            count2[ord(s2[i]) - ord('a')] += 1
        if count1 == count2:
            return True
        for i in range(len(s1), len(s2)):
            count2[ord(s2[i]) - ord('a')] += 1
            count2[ord(s2[i - len(s1)]) - ord('a')] -= 1
            if count1 == count2:
                return True
        return False
            
```

The code can be explained in the following steps:

1. create a list of length 26 to keep track of the count of characters
    
2. create an early exit condition where if len(s1) &gt; len(s2) then we know it is False
    
3. count all the characters that appear in s1 and start looping through s2 to check if at any point they are the same
    

**Time Complexity:**

O(N) Since we only looping through each string ounce and checking, adding to a list is constant time

**Space Complexity:**

Since we have two fixed length lists the time complexity O(1) or constant time