567. Permutation in String — LeetCode(Python)

I got you!

Problem:

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.

Solution:

if len(s1) > len(s2):
    return False
        
s1ctr,  s2ctr = [0] * 26, [0] * 26
        
for i in range(len(s1)):
    s1ctr[ord(s1[i]) - ord('a')] += 1
    s2ctr[ord(s2[i]) - ord('a')] += 1
            
matches = 0
for i in range(26):
    matches += (1 if  s1ctr[i] == s2ctr[i] else 0)
            
l = 0
for r in range(len(s1), len(s2)):
    if matches == 26:
        return True
            
    # for sliding the right end of the window
    index = ord(s2[r]) - ord('a') #find what character has been added to window
    s2ctr[index] += 1 #increment character's count in counter array
    if s1ctr[index] == s2ctr[index]: #if frequencies same
        matches += 1                 #then matches++
    elif s1ctr[index] + 1 == s2ctr[index]:#if frequency is increased in s2ctr after adding this new character
        matches -= 1                 #then matches--
                
    # for sliding left end of window
    index = ord(s2[l]) - ord('a') # find what character has been removed from window
    s2ctr[index] -= 1 # decrement the character's count in counter array
    if s1ctr[index] == s2ctr[index]: # if removing that character equals both counts
        matches += 1                 #mathces ++
    elif s1ctr[index] - 1 == s2ctr[index]: #if frequency is decrased in s2ctr after removing from left
        matches -= 1                      #matches--
                
    l += 1 #keep sliding the window
            
return matches == 26

Explanation —

We use the sliding window technique here.

We keep two hash maps for s1 and window in s2 of length == len(s1).

The s1ctr dictionary stores the frequency of each element in s1. And the s2ctr dictionary stores the frequency of each element in the window in s2 that we are currently considering.

If the frequency of each element in both hash maps is the same, the string has been found and we return True.

First, we initialize both the hash maps up to length == len(s1). After that, we count the number of matches in both s1ctr and s2ctr.

Now, we slide the window from len(s1), where we are, after initializing the two maps, up to len(s2).

We return True if matches == 26, i.e the frequency of each alphabet is the same in both strings.

We slide the window from the right first, check which character was added, increment it’s count in the map, and update the number of matches accordingly.

Next, we check what character is going to be removed from the left, decrement the character’s count in the map, and update the number of matches accordingly. After that we shrink the window from the left.

Finally, we could have returned False, but we return matches == 26, for the case where matches was made equal to 26 in the last possible window which could not be checked in the for loop.

Time Complexity —

We need a constant amount of space, since we are given that —

s1 and s2 consist of lowercase English letters.

Also, our algorithm requires us to visit each string character at most once, which is a linear time operation.

Thus, if n is the length of the string s2,

Time Complexity: O(n)

Space Complexity: O(26) or O(1) [amortized]

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏