MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Permutation in String

Written By ## Permutation in String Introduction

The Permutation in String problem asks us to return true if one of s1's permutations is the substring of s2. This problem can be solved using a combination of a sliding window approach and the usage of frequency maps. The frequency map will store the count of each character in the respective strings.

## Permutation in String 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 Inputs and Outputs

#### Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: True

#### Example 2

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

## Permutation in String Solutions

To solve this problem, we can use a sliding window approach. First, we create two frequency maps: one for string s1 and one for the current window in string s2. The frequency map will store the count of each character in the respective strings.

We start by initializing the frequency maps for both strings. Then, we set up a window of length equal to the length of s1 in string s2. We compare the frequency maps of s1 and the window of s2. If they are equal, it means that the window in s2 contains a permutation of s1, and we return true. Next, we move the window by one character to the right in s2 and update the frequency maps accordingly. We remove the character that just went out of the window from the frequency map, and we add the new character that came into the window.

We repeat this process until we have exhausted all possible windows in s2. If we have not found a matching permutation, we return false.

``````from collections import Counter

def checkInclusion(s1, s2):
len_s1 = len(s1)
len_s2 = len(s2)

if len_s1 > len_s2:
return False

freq_s1 = Counter(s1)
freq_window = Counter(s2[:len_s1])

if freq_s1 == freq_window:
return True

for i in range(len_s1, len_s2):
char_out = s2[i - len_s1]
if freq_window[char_out] == 1:
del freq_window[char_out]
else:
freq_window[char_out] -= 1

char_in = s2[i]
freq_window[char_in] += 1

if freq_s1 == freq_window:
return True

return False

# Test case
s1 = "ab"
s2 = "eidbaooo"
result = checkInclusion(s1, s2)
print(result)  # Expected output: True``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), where N is the length of s2, as we iterate through each character once.
• Space Complexity: O(1), as the frequency maps have a fixed size of 26 lowercase letters.