Checking for Permutations in Strings: A Sliding Window Approach

The task is to determine if one string contains a permutation of another.

The latter is part of string manipulation and pattern matching.

The sliding window technique will be handy in solving substring-related problems like this one.

Why?

This method will save you time and computational resources.

Example 1: Result is True

`string1 = "ab"` 
`string2` = "eidbaooo"`

#`string2` contains a permutation of the `string1`.

Example 2: Result is False

`string1` = "ab"` 
`string2` = "eidboaoo"`

#`string2`  does not contain a permutation of `string1`

Naive solution pseudocode

• We first generate all permutations of `string1`.

• Subsequently, find if any of the permutations exist in `string2`. 

The algorithm's time is O(N!), where N is the length of `string1`. 

Sliding Window with Frequency Counting  

It combines the sliding window and the frequency counter techniques.

The Steps:-

• Create two arrays, `count1` and `count2` ->the frequency Arrays.
  • Use the arrays to store the frequency of each character in `s1` and the current window of `s2`, respectively.
• Populate `count1` with the character counts of `s1` and `count2` with the character counts of the first window of `s2` (of size `len(s1)`).
• Slide the window through `s2`, updating `count2` by adding the new character and removing the old character.
• Compare count1 and count2 after every slide. If there is a match, it means the current window in `s2` is a permutation of `s1`.

from typing import List

class PermutationInStrings:

   def check_inclusion(self, s1: str, s2: str) -> bool:
      
      """
      Check if any permutation of s1 exists as a substring in s2.

      Args:
         s1 (str): The string to check permutations for.
         s2 (str): The string to search within.

      Returns:
        bool: True if a permutation of s1 exists in s2, False otherwise.
     """

     len1, len2 = len(s1), len(s2)

     # permutation is possible: If s1 is longer than s2 
     if len1 > len2:
        return False

     # Initialize frequency arrays for s1 and the current window in s2
     count1 = [0] * 26  # Frequency count for s1
     count2 = [0] * 26  # Frequency count for the current window in s2

     # Populate frequency arrays for the first window
     for i in range(len1):
         count1[ord(s1[i]) - ord('a')] += 1  # Increment count for s1
         count2[ord(s2[i]) - ord('a')] += 1  # Increment count for s2's first window

     # Compare the frequency arrays for the first window
     if count1 == count2:
         return True

     # Slide the window through s2
     for i in range(len1, len2):
         # Add the new character to the window
         count2[ord(s2[i]) - ord('a')] += 1
         # Remove the old character from the window
         count2[ord(s2[i - len1]) - ord('a')] -= 1
         
     # Compare the frequency arrays
     if count1 == count2:
           return True

     return False

Why This Approach Works

• Efficiency: time complexity of **O(N)**, where N is the length of `s2`.
• Space Optimization: O(1).
• No Permutations Generated:  generating all permutations is expensive

Alternative Solution

from collections import Counter

def check_inclusion(s1: str, s2: str) -> bool:

      """
      Check if any permutation of s1 exists as a substring in s2.
      """
      len1, len2 = len(s1), len(s2)

      if len1 > len2:
         return False

      count1 = Counter(s1)
      count2 = Counter(s2[:len1]) # frequency for the first window of s2

      # Slide the window across s2
      for i in range(len1, len2):
          if count1 == count2:
             return True

      # Add new character to the window
      count2[s2[i]] += 1

      # Remove the character that goes out of the window
      count2[s2[i - len1]] -= 1

      # Clean up zero counts
      if count2[s2[i - len1]] == 0:
           del count2[s2[i - len1]]

      return count1 == count2  # Final comparison for the last window

print(check_inclusion("ab", "eidbaooo"))  # Output: True

Why is this better?

• Same O(n) complexity (sliding window + Counter comparison).
• More readable (removes manual ASCII calculations).
• Use Counter for easy frequency tracking instead of fixed-size lists.
• Reduce redundant comparisons ->  zero-count keys clean-up.

Without unnecessary computations, we can tell if a permutation is present with the help of frequency counting.

Next Steps

• Do it yourself! 
• Explore edge cases:-
  • - Empty strings
  • - String one is longer than the second string
  • - String whose characters are repeated
• Explore related problems. These include:-
  • 1) finding anagrams 
  • 2) the smallest substring containing all characters of another string.

By mastering this approach, you'll be well-equipped to tackle similar challenges in your coding journey.

Happy coding!