Skip to content

567. Permutation In String

Hash Table Two Pointers String Sliding Window

Problem - Permutation In String

Medium

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from collections import Counter

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1_len, s2_len = len(s1), len(s2)

        if (s1_len > s2_len):
            return False

        s1_count = Counter(s1)

        # sliding window
        window = Counter(s2[:s1_len])

        if (s1_count == window):
            return True

        for i in range (s1_len, s2_len):
            window[s2[i]] += 1

            window[s2[i - s1_len]] -= 1

            if (window[s2[i - s1_len]] == 0):
                del window[s2[i - s1_len]]

            if (s1_count == window):
                return True
        return False

Submission Stats:

  • Runtime: 94 ms (22.19%)
  • Memory: 16.6 MB (100.00%)