Permutation in String

Problem

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

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:sup:`4`

• s1 and s2 consist of lowercase English letters.

Pattern

Hash Table, Two Pointers, String, Sliding Window

Approaches

Sliding Window

Code

from collections import Counter, defaultdict


def checkInclusion(s1: str, s2: str) -> bool:
    n = len(s1)
    if n > len(s2):
        return False

    s1_multiset = Counter(s1)
    window_multiset = defaultdict(int)

    for i in range(n):
        window_multiset[s2[i]] += 1

    for key, val in s1_multiset.items():
        if window_multiset[key] != val:
            break
    else:
        return True

    for i in range(n, len(s2)):
        window_multiset[s2[i]] += 1
        window_multiset[s2[i - n]] -= 1

        for key, val in s1_multiset.items():
            if window_multiset[key] != val:
                break
        else:
            return True

    return False

Test

>>> from permutation_in_string__sliding_window import checkInclusion
>>> checkInclusion("ab", "eidbaooo")
True
>>> checkInclusion("ab", "eidboaoo")
False

permutation_in_string__sliding_window.checkInclusion(s1: str, s2: str) → bool