567.Permutation_in_String(Medium).md

567. Permutation in String (Medium)

Date and Time: Jul 13, 2024, 15:30 (EST)

Link: https://leetcode.com/problems/permutation-in-string/

Question:

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:

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.

KeyPoints:

We can use the same method of sliding window technique in [76.Minimum Window Substring]. We are using two hashmaps (s1Map, s2Map) to compare, and two variables (countS1, countS2) to save the matches count. We use a window length = len(s1) to update the s2Map, countS2 as the window changes, and return True if we found countS1 == countS2.

We first created countS1, s1Map to save s1, then use a window of only len(s1) = countS1 to loop over s2 and save the elements with its occurence within the window. We add s2[r] into s2Map, if s2[r] is in s1Map and current s2Map[s2[r]] <= s1Map[s2[r]] we increment countS2, if countS2 == countS1, there is a permutation of s1 in s2 substring.

Finally, once r + 1 >= countS1 the r reaches the bound of the window, so we remove the lth index from s2Map and update countS2 accordingly (if s2[l] in s1Map and s2Map[s2[l]] < s1Map[s2[l]]) we decrement countS2 and move l += 1.

Example 1: the window is changing from [ei] -> [id] -> [db] -> [ba]

My Solution:

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        countS1, s1Map = len(s1), {}
        # Save s1 into hashmap
        for i in s1:
            s1Map[i] = 1 + s1Map.get(i, 0)
        countS2, s2Map = 0, {}
        l = 0
        for r in range(len(s2)):
            s2Map[s2[r]] = 1 + s2Map.get(s2[r], 0)
            if s2[r] in s1Map and s2Map[s2[r]] <= s1Map[s2[r]]:
                countS2 += 1
            # If we found the permutation
            if countS2 == countS1:
                return True  
            # if r reaches the bound of the window, update s2Map and l
            if r + 1 >= countS1:
                s2Map[s2[l]] -= 1
                if s2[l] in s1Map and s2Map[s2[l]] < s1Map[s2[l]]:
                    countS2 -= 1
                l += 1
        return False

Time Complexity: $O(len(s1) + len(s2))$ because we loop over s1, s2.
Space Complexity: $O(len(s1) + len(s2))$ because we creating two hashmaps to store s1, s2.