Permutation in String

Problem Id: 567 Difficulty: Medium


Intuition

Solution


class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        counts = {}
        for c in s1:
            if c not in counts:
                counts[c] = 0
            counts[c] -= 1

        for i in range(len(s1)):
            c = s2[i]
            if c not in counts:
                counts[c] = 0
            counts[c] += 1
            if counts[c] == 0:
                counts.pop(c)

        if not counts:
            return True
        for i in range(len(s1), len(s2)):
            c = s2[i]
            if c not in counts:
                counts[c] = 0
            counts[c] += 1
            if counts[c] == 0:
                counts.pop(c)
            c = s2[i - len(s1)]
            if c not in counts:
                counts[c] = 0
            counts[c] -= 1
            if counts[c] == 0:
                counts.pop(c)
            if not counts:
                return True
        return False