Incorrect sliding window algorithm (in python)

Question

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

Muhteva · Accepted Answer · 2022-03-07 08:03:01Z

1

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.

answered Mar 7, 2022 at 8:03

Muhteva

2,8402 gold badges12 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Incorrect sliding window algorithm (in python)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related