Leetcode Daily Question 05/10/2024 - 567. Permutation in String

Problem 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.

class Solution:
  def checkInclusion(self, s1: str, s2: str) -> bool:
    m = len(s1)
    n = len(s2) 
    
    if m > n:
      return False
    
    freq_count_s1 = [0] * 26
    freq_count_s2 = [0] * 26
    
    for i in range(m):
      freq_count_s1[ord(s1[i]) - 97] += 1
      freq_count_s2[ord(s2[i]) - 97] += 1
    
    if freq_count_s1 == freq_count_s2:
      return True
    
    for i in range(m, n):
      freq_count_s2[ord(s2[i]) - 97] += 1
      freq_count_s2[ord(s2[i - m]) - 97] -= 1
      if freq_count_s1 == freq_count_s2:
        return True
    
    return False

Explanation:

The idea is to check each substring of length equal to s1 in s2, and see if the character frequencies of that substring matches that of s1.

A substring is a contiguous part of the original string. So, to search through each substring, we start by checking the substring starting at index 0 with length equalling s1.

Then we move right one move at a time, adding the newly encountered character to our frequency array and removing the frequency of the leftmost character to correct the length of substring.

Let us use an example to illustrate.

s1 = "abc"
s2 = "edjfbac"

# Initiate the two counter arrays with s1 and s2 with substring of length s1 starting at 0
freq_count_s1 = [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# "edj"
freq_count_s2 = [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
                 
Then we move substring in s2 to the right by 1.
"edj" -> "edjf" -> "djf"
freq_count_s2 = [0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

"djf" -> "djfb" -> "jfb"
freq_count_s2 = [0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

"jfb" -> "jfba" -> "fba"
freq_count_s2 = [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

"fba" -> "fbac" -> "bac"
freq_count_s2 = [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Now, freq_count_s1 == freq_count_s2, so we return True

Putting this into code.

def checkInclusion(s1, s2):
  m = len(s1)
  n = len(s2)
  
  if m > n: # If length of s1 > length of s2, then s2 cannot have substring equalling to s1.
    return False
  
  freq_count_s1 = [0] * 26
  freq_count_s2 = [0] * 26
  
  for i in range(m):
    freq_count_s1[ord(s1[i]) - 97] += 1
    freq_count_s2[ord(s2[i]) - 97] += 1
    
  if freq_count_s1 == freq_count_s2:
    return True
  
  for i in range(m, n):
    freq_count_s2[ord(s2[i]) - 97] += 1 # Add a new char on the right
    freq_count_s2[ord(s2[i - m]) - 97] -= 1 # Remove leftmost 
    if freq_count_s1 == freq_count_s2:
      return True
    
  return False

The time complexity is O(n) as we iterate through s2 to compare each substring.

The space complexity is O(1) since we only store two fixed length array.

The full solution can be found near the top of the page.