[Python][LeetCode] 567. Permutation in String

Link

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        # point 1. How to use 'Counter' as class by import
        cntr, w = Counter(s1), len(s1)   
        # s1 = 'abc', s2 = 'cidbacoo'
        # Counter -> {"a": 1, "b": 1, "c": 1}

        for i in range(len(s2)):
            if s2[i] in cntr: 
                cntr[s2[i]] -= 1
            # 1st window: "cid" in s2
            # 'c' is in s1
            # Counter -> {"a": 1, "b": 1, "c": 0} (c: 1 -> 0)

            if i >= w and s2[i-w] in cntr: 
                cntr[s2[i-w]] += 1
        # 2nd window: "idb" in s2
        # 'b' is a character from s1, so cntr['b'] is decreased by 1 (making cntr['b'] equal to 0).
        
        # 'c' is not in "idb", and c place on s2[i-w] (i=3 while looping, w = 3 is fixed)
        # and as you can see the condition of "if i >= w and s2[i-w] in cntr: "
        # you have to "cntr[s2[i-w]] += 1", it means "contr[s2[3-3]]" -> "cntr[s2[0]]" -> "cntr[c]" 
        # -> Counter -> {"a": 1, "b": 0, "c": 1} (c: 0 -> 1) (Cz now window is "idb")

            if all([cntr[i] == 0 for i in cntr]): # see optimized code below
                return True

        return False

Summary

• point 1. How to use ‘Counter’ as class by import

s1 = ‘abc’, s2 = ‘cidbacoo’

Counter -> {“a”: 1, “b”: 1, “c”: 1}

• point 2. Example

We have to notice this code.

if i >= w and s2[i-w] in cntr:

Let’s see the proceed of whole code.

1st window: “cid” in s2.

‘c’ is in s1

Counter -> {“a”: 1, “b”: 1, “c”: 0} (c: 1 -> 0).

2nd window: “idb” in s2.

‘b’ is a character from s1, so cntr[‘b’] is decreased by 1 (making cntr[‘b’] equal to 0).

‘c’ is not in “idb”, and c place on s2[i-w] (i=3 while looping, w = 3 is fixed). and as you can see the condition of “if i >= w and s2[i-w] in cntr: “

you have to “cntr[s2[i-w]] += 1”, it means “contr[s2[3-3]]” -> “cntr[s2[0]]” -> “cntr[c]”

-> Counter -> {“a”: 1, “b”: 0, “c”: 1} (c: 0 -> 1) (Cz now window is “idb”)