0567 Minimum Window Substring

0567 Minimum Window Substring#

Problem#

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.

Examples#

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 <= 104
s1 and s2 consist of lowercase English letters.

Followup#

Analysis#

  • How to check if one is a permutation of the other?

    • Method 1: brute force -> generate all the permutations

    • Method 2: check if the occurrences of characters are the same

Solution#

def checkPermutation(s1, s2):
    ns1, ns2 = len(s1), len(s2)
    # special case
    if ns1 > ns2:
        return False

    # hash table for s1, storing character occurence
    s1_map = {c:s1.count(c) for c in s1}
    # initialize s1 map
    s2_map = {}

    # initialize a sliding window
    left, right = 0, 0

    # main
    while right < ns2:
        c = s2[right]
        s2_map[c] = s2_map[c]+1 if c in s2_map else 1
        right += 1

        # maitain a fixed length of window
        while right - left >= ns1:
            # determine if s1 is a permutation of s1
            if s1_map == s2_map:
                return True
            
            # remove left char from s2_map
            c = s2[left]
            s2_map[c] -= 1
            if s2_map[c] == 0: s2_map.pop(c)
            
            # shrink the window 
            left += 1

    return False

# test
s1 = "ab" 
s2 = "eidbaooo"
print(checkPermutation(s1, s2))

s1 = "ab" 
s2 = "eidboaoo"
print(checkPermutation(s1, s2))

True
False
Contents