Permutation in String

Patrick Leaton
Published: June 24, 2021, 8:05 p.m.
Problem Description

Given two strings s1 and s2, return true if s2 contains the permutation of s1.

In other words, one of s1's permutations is the substring of s2.

 

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:

  • 1 <= s1.length, s2.length <= 10^4
  • s1 and s2 consist of lowercase English letters.

 

The description was taken from https://leetcode.com/problems/permutation-in-string/

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
       
        s1_chars, s2_chars = {}, {}
        left, right = 0, 0
       
        for char in s1:
            if char not in s1_chars:
                s1_chars[char] = 1
            else:
                s1_chars[char] += 1
       
        while right < len(s1)-1:
            if s2[right] not in s2_chars:
                s2_chars[s2[right]] = 1
            else:
                s2_chars[s2[right]] += 1
            right += 1
       
        while right < len(s2):
            if s2[right] not in s2_chars:
                s2_chars[s2[right]] = 1
            else:
                s2_chars[s2[right]] += 1
           
            if s1_chars == s2_chars:
                return True
           
            s2_chars[s2[left]] -= 1
            if s2_chars[s2[left]] == 0:
                del s2_chars[s2[left]]
 
            left += 1
            right += 1
               
        return False

Problem Explanation

This problem is very similar to Find All Anagrams in a String.

The most straightforward way to solve this is to sort both strings then have a sliding window then continuously check if the substring is in the string window.

A better, faster way to solve this is to compare the frequency of characters between both strings through a sliding window and a couple of hashmaps.  We will create a fixed set window the size of the substring, and we will continuously compare the hashmap of the substring character frequencies against the other string's hashmap of character frequencies.  If we have the same frequency between the two, we have a permutation in the string.

First off, if the substring is larger than the other string, then the string can't possibly contain a permutation of the substring.

In that case, we will return false.

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

 

Next, we will create the two hashmaps for character frequencies between the two strings then our left and right pointers.

        s1_chars, s2_chars = {}, {}
        left, right = 0, 0

 

Afterward, we will push each character of the substring into the substring's frequency hashmap.

If the character is already there, we will just increment the frequency.

If not, we will initialize the frequency to once.

        for char in s1:
            if char not in s1_chars:
                s1_chars[char] = 1
            else:
                s1_chars[char] += 1

 

Then, we will push characters from the other string into its frequency hashmap, up to one place behind the size of the substring.

The reason being we will add that last character into our hashmap during our sliding window so that we can have an initial window size equal to the substring.  

The frequency incrementing process will be the same as the previous loop.

        while right < len(s1)-1:
            if s2[right] not in s2_chars:
                s2_chars[s2[right]] = 1
            else:
                s2_chars[s2[right]] += 1
            right += 1

 

Now we will begin our sliding window.

        while right < len(s2):

 

Just like other sliding window problems, our right pointer will be in charge of throwing values into the window.  The left will be in charge of evicting values from it.

Let's throw the character at the right pointer into the window.

            if s2[right] not in s2_chars:
                s2_chars[s2[right]] = 1
            else:
                s2_chars[s2[right]] += 1

 

If the string and substring's character frequencies match, we have a valid permutation.

If that is the case we can stop now and return true.

            if s1_chars == s2_chars:
                return True

 

We will need to evict the left pointer's character from the window and the string's hashmap if it's not the case.

We will do this by incrementing the frequency value, but we also need to check if that frequency is now zero.

If it is, we will delete that key from our hashmap.  If our window does come across the permutation later, we won't be able to tell because our hashmaps won't be equal, since that zero frequency character will still be in one of them.

            s2_chars[s2[left]] -= 1
            if s2_chars[s2[left]] == 0:
                del s2_chars[s2[left]]

 

Once we do that, we will continue moving our pointers down the string.

            left += 1
            right += 1

 

This isn't a traditional sliding window problem since our window is of a fixed size and it never expands or contracts, but we will continue moving along no matter what until we find the answer or run out of characters.

If we have gotten to the end of the string and haven't found the right character recipe for the substring, we will return false because we never got to eat that alphabet soup.

        return False