LC-0567 Medium LeetCode

567. Permutation in String

Hash Table Two Pointers String Sliding Window

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 47% Topics: Hash Table, Two Pointers, String, Sliding Window

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Strings 12 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

import collections


class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        counts = collections.Counter(s1)
        l = len(s1)
        for i in xrange(len(s2)):
            if counts[s2[i]] > 0:
                l -= 1
            counts[s2[i]] -= 1
            if l == 0:
                return True
            start = i + 1 - len(s1)
            if start >= 0:
                counts[s2[start]] += 1
                if counts[s2[start]] > 0:
                    l += 1
        return False

Solution from kamyu104/LeetCode-Solutions · MIT