# Permutation in String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/permutation-in-string)
Canonical: https://scaleengineer.com/dsa/problems/permutation-in-string
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Hash Table, String
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Cisco](https://scaleengineer.com/companies/cisco), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Yandex](https://scaleengineer.com/companies/yandex), [Revolut](https://scaleengineer.com/companies/revolut)
---
## 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 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

**Constraints:**

* `1 <= s1.length, s2.length <= 104`
* `s1` and `s2` consist of lowercase English letters.

# Approaches
## Sorting Substrings
This approach is based on the property that two strings are permutations of each other if and only if their sorted versions are identical. We can iterate through all substrings of `s2` that have the same length as `s1`. For each substring, we sort it and compare it with a pre-sorted version of `s1`.
**Time:** O((m-n) * n log n). Let `n` be the length of `s1` and `m` be the length of `s2`. Sorting `s1` initially takes `O(n log n)`. The main loop runs `m-n+1` times. Inside the loop, creating a substring takes `O(n)` and sorting it takes `O(n log n)`. This dominates, leading to the overall complexity. · **Space:** O(n), where `n` is the length of `s1`. This space is required to store the character arrays for `s1` and the substrings of `s2` for sorting.
**Pros:** Conceptually straightforward and easy to implement.
**Cons:** Highly inefficient for large strings due to the repeated sorting of substrings within a loop.; Very likely to result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The core idea is to check every possible substring of `s2` of length `s1.length()` and see if it's an anagram of `s1`. A reliable way to check for anagrams is to sort both strings and see if they become equal. While simple, this method involves a costly sorting operation inside a loop, which affects its performance significantly.

```java
import java.util.Arrays;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int n = s1.length();
        int m = s2.length();

        char[] s1Chars = s1.toCharArray();
        Arrays.sort(s1Chars);

        for (int i = 0; i <= m - n; i++) {
            char[] subChars = s2.substring(i, i + n).toCharArray();
            Arrays.sort(subChars);
            if (Arrays.equals(s1Chars, subChars)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Let `n` be the length of `s1` and `m` be the length of `s2`.
- If `n > m`, it's impossible for `s2` to contain a permutation of `s1`, so return `false`.
- Convert `s1` to a character array and sort it. This gives a canonical representation of `s1`'s permutations.
- Iterate through `s2` with a window of size `n`. The loop runs from `i = 0` to `m - n`.
- For each window (substring of `s2` from `i` to `i + n - 1`):
  - Convert the substring to a character array and sort it.
  - Compare the sorted substring with the sorted `s1`.
  - If they are identical, it means the substring is a permutation of `s1`. Return `true`.
- If the loop completes without finding any match, return `false`.

## Sliding Window with Frequency Map
A much more efficient method is to use the sliding window technique. We can determine if two strings are permutations by comparing their character frequency maps. We maintain a fixed-size window of length `len(s1)` that slides across `s2`. Instead of re-computing the frequency map for the window in each step, we efficiently update it by subtracting the character that leaves the window and adding the character that enters.
**Time:** O(n + (m-n)) = O(m). Let `n` be `s1.length()` and `m` be `s2.length()`. We take `O(n)` to build the initial frequency maps. Then, we iterate `m-n` times. In each step, updating the map is `O(1)`, and comparing the maps takes `O(k)` where `k` is the alphabet size (26). Since `k` is constant, the total time complexity is linear with respect to the length of `s2`. · **Space:** O(1). We use two arrays of a fixed size 26 to store character frequencies. Since the alphabet size is constant, the space complexity is constant.
**Pros:** Optimal time complexity, making it very fast for large inputs.; Constant space complexity as the space used does not depend on the input string sizes.
**Cons:** Slightly more complex to reason about and implement compared to the naive sorting approach.
### Explanation
This approach avoids the expensive sorting operation. By using frequency maps (arrays of size 26 for lowercase letters), we can check for permutations in `O(1)` time (or `O(k)` where `k` is the alphabet size, which is constant). The sliding window allows us to reuse the computation from the previous window. We only need to adjust the counts for two characters at each step: the one leaving the window and the one entering. This leads to a linear time solution.

```java
import java.util.Arrays;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }

        int[] s1Map = new int[26];
        int[] s2Map = new int[26];

        // Initialize maps for the first window
        for (int i = 0; i < n; i++) {
            s1Map[s1.charAt(i) - 'a']++;
            s2Map[s2.charAt(i) - 'a']++;
        }

        // Slide the window across s2
        for (int i = 0; i < m - n; i++) {
            if (Arrays.equals(s1Map, s2Map)) {
                return true;
            }
            // Slide the window forward
            // Add the new character entering the window from the right
            s2Map[s2.charAt(i + n) - 'a']++;
            // Remove the character leaving the window from the left
            s2Map[s2.charAt(i) - 'a']--;
        }

        // Final check for the last window
        if (Arrays.equals(s1Map, s2Map)) {
            return true;
        }

        return false;
    }
}
```
### Algorithm
- Let `n` be the length of `s1` and `m` be the length of `s2`. If `n > m`, return `false`.
- Since the strings consist of lowercase English letters, we can use two integer arrays of size 26, `s1Map` and `s2Map`, as frequency maps.
- Populate `s1Map` with the character frequencies of `s1`.
- Populate `s2Map` with the character frequencies of the first window of `s2` (i.e., the first `n` characters).
- Compare `s1Map` and `s2Map`. If they are identical, a permutation is found. Return `true`.
- Slide the window one character at a time from left to right across `s2`. The loop runs from `i = n` to `m-1`.
- In each step of the slide:
  - Add the new character entering the window: increment the count for `s2.charAt(i)` in `s2Map`.
  - Remove the old character leaving the window: decrement the count for `s2.charAt(i - n)` in `s2Map`.
  - After updating the window's map (`s2Map`), compare it with `s1Map`. If they are equal, return `true`.
- If the loop finishes without finding a match, return `false`.

# Solutions
### Java

```java
class Solution { public boolean checkInclusion ( String s1 , String s2 ) { int n = s1 . length (); int m = s2 . length (); if ( n > m ) { return false ; } int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < n ; ++ i ) { -- cnt [ s1 . charAt ( i ) - 'a' ]; ++ cnt [ s2 . charAt ( i ) - 'a' ]; } int diff = 0 ; for ( int x : cnt ) { if ( x != 0 ) { ++ diff ; } } if ( diff == 0 ) { return true ; } for ( int i = n ; i < m ; ++ i ) { int a = s2 . charAt ( i - n ) - 'a' ; int b = s2 . charAt ( i ) - 'a' ; if ( cnt [ b ] == 0 ) { ++ diff ; } if (++ cnt [ b ] == 0 ) { -- diff ; } if ( cnt [ a ] == 0 ) { ++ diff ; } if (-- cnt [ a ] == 0 ) { -- diff ; } if ( diff == 0 ) { return true ; } } return false ; } }
```

### CSharp

```csharp
public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        int need = 0;
        int[] cnt = new int[26];
        foreach(char c in s1) {
            if (++cnt[c - 'a'] == 1) {
                need++;
            }
        }
        int m = s1.Length, n = s2.Length;
        for (int i = 0; i < n; i++) {
            int c = s2[i] - 'a';
            if (--cnt[c] == 0) {
                need--;
            }
            if (i >= m) {
                c = s2[i - m] - 'a';
                if (++cnt[c] == 1) {
                    need++;
                }
            }
            if (need == 0) {
                return true;
            }
        }
        return false;
    }
}
```

### CPP

```cpp
class Solution {
public:
  bool checkInclusion(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    if (n > m) {
      return false;
    }
    vector<int> cnt(26);
    for (int i = 0; i < n; ++i) {
      --cnt[s1[i] - 'a'];
      ++cnt[s2[i] - 'a'];
    }
    int diff = 0;
    for (int x : cnt) {
      if (x) {
        ++diff;
      }
    }
    if (diff == 0) {
      return true;
    }
    for (int i = n; i < m; ++i) {
      int a = s2[i - n] - 'a';
      int b = s2[i] - 'a';
      if (cnt[b] == 0) {
        ++diff;
      }
      if (++cnt[b] == 0) {
        --diff;
      }
      if (cnt[a] == 0) {
        ++diff;
      }
      if (--cnt[a] == 0) {
        --diff;
      }
      if (diff == 0) {
        return true;
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution : def checkInclusion ( self , s1 : str , s2 : str ) -> bool : n , m = len ( s1 ), len ( s2 ) if n > m : return False cnt = Counter () for a , b in zip ( s1 , s2 ): cnt [ a ] -= 1 cnt [ b ] += 1 diff = sum ( x != 0 for x in cnt . values ()) if diff == 0 : return True for i in range ( n , m ): a , b = s2 [ i - n ], s2 [ i ] if cnt [ b ] == 0 : diff += 1 cnt [ b ] += 1 if cnt [ b ] == 0 : diff -= 1 if cnt [ a ] == 0 : diff += 1 cnt [ a ] -= 1 if cnt [ a ] == 0 : diff -= 1 if diff == 0 : return True return False
```