Medium

Permutation in String

LAB

Return true if s2 contains any permutation of s1 as a substring.

EXAMPLES

Example 1

Input
{
  "s1": "ab",
  "s2": "eidbaooo"
}

Output
true

FUNCTION SHAPE

s1: strings2: string→bool

SOLUTION NOTE

We track how many characters have been fully matched (count). When count equals the number of unique characters in s1, we've found a permutation.

Reveal reference solution +

pythonREFERENCE

def checkInclusion(self, s1: str, s2: str) -> bool:
    k = len(s1)
    window = Counter(s1)
    count = 0
    set_ = set(s1)

    for i in range(len(s2)):
        if s2[i] in set_:
            window[s2[i]] -= 1
            if window[s2[i]] == 0:
                count += 1

        if i >= k - 1:
            if count == len(set_):
                return True

            if s2[i - (k - 1)] in set_:
                window[s2[i - (k - 1)]] += 1
                if window[s2[i - (k - 1)]] == 1:
                    count -= 1

    return False

TimeO(n)

SpaceO(26) = O(1)

Open on LeetCode ↗