Leetcode 567. Permutation in String

Problem

Leetcode 567 - Permutation in String

Example:

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

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

Approach

We can approach this problem by using two pointer and two dict to keep track of s1’s character frequency and s2 window’s character frequency.

We leave the left pointer on the first element of the s2 and we can iterate through the character in s2 (as right pointer).

We can first see len(s1) > len(s2), if so then we just return False

We can then count the frequencies of s1, and s2[:len(s1)] to see if they match, and if they do we return True

Then we iterate through s2’s window

• decrement s2[left] from s2 dict
• delete s2[left] from s2 dict if frequncy == 0
• increment s2[right] from s2 right
• check if s1_map == s2_map

Visualization of the Approach:

s1 = 'ab', s2 = 'eidbaooo'
s1_map = { a: 1, b: 1}
s2_map = { e: 1, i: 1}

start shifting the window in s2
s2_map = { i: 1, d: 1}

s2_map = { d: 1, b: 1}

s2_map = { b: 1, a: 1}

Since s1_map == s2_map, we return True

return True

Here is the Python code for the solution:

class Solution:
     def checkInclusion(self, s1: str, s2: str) -> bool:
          if len(s1) > len(s2):
               return False
          
          s1_map, s2_map = {}, {}
          left = 0

          for i in range(len(s1)):
               s1_map[s1[i]] = 1 + s1_map.get(s1[i], 0)
               s2_map[s2[i]] = 1 + s2_map.get(s2[i], 0)
          
          if s1_map == s2_map:
               return True
          
          for r in range(len(s1), len(s2)):
               # move the window
               s2_map[s[left]] -= 1

               # remove elements that is 0
               if s2_map[s[left]] == 0:
                    del s2_map[s[left]]
               left += 1

               s2_map[s[r]] = s2_map.get(s2[r], 0)
               if s1_map == s2_map:
                    return True
          return False

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$, we can optimize this better if we use array to track of alphabets since limitation says that both strings only consists of alphabets. then it would be $O(1)$