LeetCode: Permutation in String
Tags: leetcode, datastructures, algorithms, slidingwindow
Published: 2020-05-19 21:31:04

---
title: LeetCode: Permutation in String
published: true
description: Day 18
tags: leetcode, datastructures, algorithms, slidingwindow
series: LeetCode May Challenge
---

### Problem Statement

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

 

**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
```

 

**Note:**

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

### Solution Thought Process

As we have to find a permutation of string `s1` , let's say that the length of `s1` is `k`. We can say that we have to check every `k` length subarray starting from 0. Let's say that length of `s2` is L. 

Let's store all the frequencies in an `int remainingFrequency[26]={0}`. Whenever we found an element we decrease it's remaining frequency.

The algorithm boils down to these step:

- Check `[0,k-1]` - this k length window, check if all the entries in the remaining frequency is 0

- Check `[1,k]` - this k length window, check if all the entries in the remaining frequency is 0

- Check `[2,k+1]` - this k length window, check if all the entries in the remaining frequency is 0

  .............................................................

  .............................................................

- Check `[windowStart+k-1,L-1]` - this k length window, check if all the entries in the remaining frequency is 0

If the frequencies are 0, then we can say that the permutation exists. For each window we have to consider the `26` values to determine if the window is an permutation.

So one thing we get hunch from here, this can be easily done in O(n) instead on any quadric time complexity.

**Why?**

When rolling over the next window, we can remove the left most element, and just add one right side element and change the remaining frequencies. This is called the sliding window technique.

### Solution

```c++
class Solution {
private:
    int remainingFrequency[26]={0};
    bool checkFrequency(int *frequency)
    {
        for(int i=0;i<26;i++)
        {
            if(frequency[i]!=0)
            {
                return false;
            }
        }
        return true;
    }
public:
    bool checkInclusion(string s1, string s2) {
        int k=s1.size();
        for(int i=0;i<k;i++)
        {
            remainingFrequency[s1[i]-'a']++;
        }
        int windowStart=0;
        for(int windowEnd=0;windowStart+k-1<s2.size();windowEnd++)
        {
            remainingFrequency[s2[windowEnd]-'a']--;
            if(windowEnd>=k-1)
            {
                if(checkFrequency(remainingFrequency))
                {
                    return true;
                }
                remainingFrequency[s2[windowStart]-'a']++;
                windowStart++;
            }
        }
        return false;
    }
};
```



### Complexity

**Time Complexity:** O(n)

**Space Complexity:** O(1)