Permutation in String

Sliding Window

Problem

Given two strings s1 and s2, write a function to return true if s2contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

For example:

Input: String="oidbcaf", Pattern="abc"
Output: True
Explanation: The string contains "bca" which
is a permutation of the given pattern.

Input: String="odicf", Pattern="dc"
Output: False
Explanation: No permutation of the pattern 
is present in the given string as a substring.

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Thought Process

• We can use a HashMap to remember the frequencies of all characters in the given pattern. Our goal will be to match all the characters from this HashMap with a sliding window in the given string.

• We have a static window size of the length of the pattern

Solution

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        char_freq = {}
        start = 0
        match = 0
        
        for i in range(len(s1)):
            if s1[i] not in char_freq:
                char_freq[s1[i]] = 0
            char_freq[s1[i]]+=1
            
            
        for end in range(len(s2)):
            letter = s2[end]
            # decrement the frequency of matched character
            if letter in char_freq:
                char_freq[letter]-=1
                if char_freq[letter] == 0: 
                    match+=1
            
            if len(char_freq) == match:
                return True
            
            if end >= len(s1)-1:
                char = s2[start]
                if char in char_freq:
                    if char_freq[char] == 0:
                        match-=1
                    char_freq[char]+=1
                start+=1
        return False
                        

Follow Up: Can you find all Anagrams in the String

def find_string_anagrams(str, pattern):
  result_indexes = []
  charFreq = {}
  match = 0
  start = 0

  for i in range(len(pattern)):
    if pattern[i] not in charFreq:
      charFreq[pattern[i]] = 0
    charFreq[pattern[i]]+=1

  for end in range(len(str)):
    letter = str[end]

    if letter in charFreq:
      charFreq[letter]-=1
      if charFreq[letter] == 0:
        match+=1
    
    if match == len(charFreq):
      result_indexes.append(start)

    if end >= len(pattern) - 1:
      char = str[start]
      if char in charFreq:
        if charFreq[char] == 0:
          match-=1
          charFreq[char]+=1
      start+=1


  return result_indexes

Key Points

• Using a frequency hash map to compare pattern's character frequency with the characters in our sliding window

• We are moving our window in the size of our pattern so that the current window size (and the characters within it) can always be compared to our pattern

• When char_freq[letter] hits 0, that means we have found all occurences of that letter in our string

• Using a static window

• Before we add the next letter, we shrink our window first

• We are comparing the len(hashMap) because haspMap has all the count of characters

Time Complexity

• Time: $O(N+M)$ where ‘N’ and ‘M’ are the number of characters in the input string and the pattern, respectively.

• Space: $O(M)$ since in the worst case, the whole pattern can have distinct characters that will go into the HashMap.