---
tags: data_structure_python
---

# Permutation in String

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

**Constraints:**

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

# Solution

### Solution 1: Dynamic variant + hashmap

class Solution:
    
    def build_hashmap(self, s):
        hashmap = {}
        for letter in s:
            if letter in hashmap:
                hashmap[letter] += 1
            else:
                hashmap[letter] = 1
        return hashmap
        
    def checkInclusion(self, s1: str, s2: str) -> bool:
        # Time complexity: O(n * len(s1)) ~= O(n).
        # Space complexity: O(len(s1) + len(s2)) ~= O(1).
        
        m, n = len(s1), len(s2)
        
        # Create hashmap for s1.
        hashmapS1 = self.build_hashmap(s1)
        nbS1Letters = sum(hashmapS1.values())
        
        # Go through s2 len(s2)-len(s1) times.
        for beg in range(n-m+1):        
            if beg == 0:
                # Create hashmap for s2.
                hashmapS2 = self.build_hashmap(s2[beg:beg+m])
            else:
                # Update window size.
                hashmapS2[s2[beg-1]] -= 1
                
                end = beg+m-1
                if s2[end] in hashmapS2:
                    hashmapS2[s2[end]] += 1
                else:
                    hashmapS2[s2[end]] = 1
                    
            # Compare both hashmaps values.
            nbS2Letters = 0
            for letter in hashmapS1:
                # Take into account only letters who belong to both hashmaps with same frequencies.
                if letter in hashmapS2 and hashmapS1[letter] == hashmapS2[letter]:
                    nbS2Letters += hashmapS2[letter]
                else:
                    break
           
            if nbS2Letters == nbS1Letters:
                return True
        
        return False