Welcome to the LeetCode Problem of the Day series! In today's edition, we'll be exploring question 567: Permutation in String. This problem challenges us to determine whether one of the permutations of a given string, s1, is a substring of another string, s2. Join me as we break down the problem, discuss the thought process, and walk through a solution step by step.
Description
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.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints:
1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.
Examination
The first thing we want to do when solving any problem is thoroughly understand what is being asked of us. What we notice when reading over this problem is that we are looking for a permutation of s1 in s2, now this might be tricky to wrap your head around if you are unfamiliar with permutations, but if we look at the examples we notice that the permutation is nothing more than an anagram essentially. So with that being said we are looking for any form of s1in s2and that can be in order or reversed, or an any order as long as the characters are consecutive.
Furthermore, when we look at the constraints we learn even more, s1 and s2 consist of lowercase English letters. what this means is that we don't have to worry about any special characters, numbers, or capitals, so, all we need to worry about is 26 letters.
Since we are looking for a string of size s1 in s2 that has to be consecutive, we know that we can use the sliding window technique.
Sure we can use a sliding window, but how can we know how far to slide it and whats in the window and whether it matches our s1? Well the answer to that is to keep two arrays that keep the count of each character in s1 and each character in s2. Once the arrays match then we know that we have found the permutation, otherwise it doesn't exist. This can be achieved by using the ascii value of each character as the index and incrementing it's count by 1 when seen.
The trick is to initialize the count array of s1 first, since this will be the reference array that we compare the count array of s2 to. Then we do the same for array 2, except after every character is added to the count array, we want to check that the window is no bigger than s1 or that will mess us up, if it is we shrink it by one from the left. After that is done, we can check if the two arrays are equivalent, and if they are then we can return true, if not return false.
Solution
class Solution(object):
def checkInclusion(self, s1, s2):
# declare variables and count arrays
n, m = len(s1), len(s2)
# we set each array to 26 values of 0 since our constraints tell us we only need to worry about 26 characters
cnt_1, cnt_2 = [0]*26, [0]*26
# Lets initialize our first count array with s1 since we will be using it as the reference
for i in range(n):
# This gets the ascii value of the value at i in s1, uses that value as the index in the count array and increments it by 1
cnt_1[ord(s1[i]) - ord('a')] += 1
# Now we do the same for the second array
for i in range(m):
cnt_2[ord([s2[i]) - ord('a')] += 1
# Ensure that the window size isn't growing past the size of s1
# What this is doing is finding the value in count array 2 that is outside of the window size that we want to maintain and removing it by decrementing by 1
if i >= n:
cnt_2[ord(s2[i-n]) - ord('a')] -= 1
# Check if the arrays match and if they do return true
if cnt_1 == cnt_2:
return True
# Other wise return False
return False
Top comments (0)