While trying this question: https://leetcode.com/problems/permutation-in-string/

"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."

I came up with a sliding window solution, but I did not want to use an additional hash table for keeping track of the letters in the current window. I am struggling to figure out why it is not correct.

Fails with this example: "trinitrophenylmethylnitramine" "dinitrophenylhydrazinetrinitrophenylmethylnitramine"

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        
        s1_ht = {}
        for char in s1:
            if char in s1_ht:
                s1_ht[char]  = 1
            else:
                s1_ht[char] = 1
        
        start = 0
        counter = len(s1_ht)
        
        for i in range(0, len(s2), 1):
                
            if s2[i] in s1_ht:
                s1_ht[s2[i]] -= 1
                if s1_ht[s2[i]] == 0:
                    counter -= 1
            
            if i - start   1 == len(s1):
                    
                if counter == 0:
                    return True
                
                if s2[start] in s1_ht:
                    s1_ht[s2[start]]  = 1
                    if s1_ht[s2[start]] > 0:
                        counter  = 1
                        
                start  = 1
        
        
        return False
                

CodePudding user response：

Great solution. But there is a minor mistake here:

if s1_ht[s2[start]] > 0:
   counter  = 1

In these lines of code, you increment the counter although s1_ht[ s2[start] ] was not zero before the incrementation. Let me explain with an example. Suppose s1_ht['t'] = 4. Then you find s2[start] = 't'. Therefore you increment s1_ht['t'] and set it equal to 5. But then you increment the counter which leads to an error. You shouldn't increment the counter since it already covers the character 't'. Swap that line with this:

if s1_ht[s2[start]] == 1:   # just before the incrementation, it was zero
   counter  = 1

It passes the Leetcode test cases with 61 ms runtime and 14 MB memory on my machine.