Leetcode 567 - Permutation in String

Understanding the problem

Given two strings s1 and s2, write a function to check if s2 is a permutation of s1.

Example:

Input: s1 = “ab” s2 = “eidbaooo”

Output: True

Explanation: s2 contains one permutation of s1 (“ba”).

Input: s1 = “ab” s2 = “eidboaoo”

Output: False

Note:

• The input strings only contain lower case letters.
• The length of s1 and s2 must not exceed 10^4.

Plan your solution

One approach to solve this problem is to use sliding window technique. We can slide a window of length len(s1) over the string s2 and check if the characters in the window are a permutation of s1. If it is, we return True. Otherwise, we slide the window by one character to the right and repeat the process until we reach the end of s2. If we have checked all the windows and none of them is a permutation of s1, we return False.

Implement your solution

Now let’s implement the solution in Python.

First, we need to define the function check_permutation(s1: str, s2: str) -> bool that takes in two strings s1 and s2 and returns a boolean indicating if s2 is a permutation of s1.

We can start by initializing a variable window to an empty list. This list will store the characters in the current window that we are checking.

Then, we can use a for loop to iterate over the characters in s2. In each iteration, we append the current character to the window list. If the length of the window list is greater than the length of s1, we remove the first character from the list. This way, the window list always stores the characters in the current window that we are checking.

Next, we can use a set and a counter to check if the characters in the window list are a permutation of s1. We can create a set s1_set from the characters in s1 and a counter counter initialized to the length of s1. Then, we can iterate over the characters in the window list and check if each character is in the s1_set. If it is, we decrement the counter by 1. Otherwise, we break the loop and continue with the next iteration.

If the counter becomes 0 at the end of the loop, it means that the window list contains a permutation of s1, so we return True.

Finally, we return False if we have checked all the windows and none of them is a permutation of s1.

Here is the implementation:

from collections import Counter

def checkInclusion(s1: str, s2: str) -> bool:
    window = []
    for c in s2:
        window.append(c)
        if len(window) > len(s1):
            window.pop(0)
        if len(window) == len(s1):
            s1_set = set(s1)
            counter = len(s1)
            for c in window:
                if c in s1_set:
                    counter -= 1
                else:
                    break
            if counter == 0:
                return True
    return False

Test your solution

Now we can test our solution with some test cases.

s1 = "ab"
s2 = "eidbaooo"
assert checkInclusion(s1, s2) == True

s1 = "ab"
s2 = "eidboaoo"
assert checkInclusion(s1, s2) == False

s1 = "abc"
s2 = "bac"
assert checkInclusion(s1, s2) == True

s1 = "abc"
s2 = "bcaa"
assert checkInclusion(s1, s2) == True

s1 = "abc"
s2 = "abcd"
assert checkInclusion(s1, s2) == False

All the test cases pass, which means our solution is correct.

That’s it! We have successfully implemented a solution to check if s2 is a permutation of s1 using the sliding window technique.

I hope this helps! Let me know if you have any questions.

Related:

• number of substrings containing all three characters
• two sum solution with code
• replace words with solution