Leetcode 567 - Permutation in String
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
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.
Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.
Related:
- number of substrings containing all three characters
- two sum solution with code
- replace words with solution