Permutation in String

Med

#0550Time: 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.6 companies

Patterns

Sliding Window Two Pointers

Data structures

Hash Table String

Companies

Agoda Cisco Expedia Goldman Sachs

Prompt

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 <= 10⁴
s1 and s2 consist of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public boolean checkInclusion(String s1, String s2) {5        if (s1.length() > s2.length()) {6            return false;7        }8        int n = s1.length();9        int m = s2.length();10 11        char[] s1Chars = s1.toCharArray();12        Arrays.sort(s1Chars);13 14        for (int i = 0; i <= m - n; i++) {15            char[] subChars = s2.substring(i, i + n).toCharArray();16            Arrays.sort(subChars);17            if (Arrays.equals(s1Chars, subChars)) {18                return true;19            }20        }21        return false;22    }23}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public boolean checkInclusion(String s1, String s2) {5        int n = s1.length(), m = s2.length();6        if (n > m) {7            return false;8        }9 10        int[] s1Map = new int[26];11        int[] s2Map = new int[26];12 13        // Initialize maps for the first window14        for (int i = 0; i < n; i++) {15            s1Map[s1.charAt(i) - 'a']++;16            s2Map[s2.charAt(i) - 'a']++;17        }18 19        // Slide the window across s220        for (int i = 0; i < m - n; i++) {21            if (Arrays.equals(s1Map, s2Map)) {22                return true;23            }24            // Slide the window forward25            // Add the new character entering the window from the right26            s2Map[s2.charAt(i + n) - 'a']++;27            // Remove the character leaving the window from the left28            s2Map[s2.charAt(i) - 'a']--;29        }30 31        // Final check for the last window32        if (Arrays.equals(s1Map, s2Map)) {33            return true;34        }35 36        return false;37    }38}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1public class Solution {2    public bool CheckInclusion(string s1, string s2) {3        int need = 0;4        int[] cnt = new int[26];5        foreach(char c in s1) {6            if (++cnt[c - 'a'] == 1) {7                need++;8            }9        }10        int m = s1.Length, n = s2.Length;11        for (int i = 0; i < n; i++) {12            int c = s2[i] - 'a';13            if (--cnt[c] == 0) {14                need--;15            }16            if (i >= m) {17                c = s2[i - m] - 'a';18                if (++cnt[c] == 1) {19                    need++;20                }21            }22            if (need == 0) {23                return true;24            }25        }26        return false;27    }28}

1class Solution {2public:3  bool checkInclusion(string s1, string s2) {4    int n = s1.size(), m = s2.size();5    if (n > m) {6      return false;7    }8    vector<int> cnt(26);9    for (int i = 0; i < n; ++i) {10      --cnt[s1[i] - 'a'];11      ++cnt[s2[i] - 'a'];12    }13    int diff = 0;14    for (int x : cnt) {15      if (x) {16        ++diff;17      }18    }19    if (diff == 0) {20      return true;21    }22    for (int i = n; i < m; ++i) {23      int a = s2[i - n] - 'a';24      int b = s2[i] - 'a';25      if (cnt[b] == 0) {26        ++diff;27      }28      if (++cnt[b] == 0) {29        --diff;30      }31      if (cnt[a] == 0) {32        ++diff;33      }34      if (--cnt[a] == 0) {35        --diff;36      }37      if (diff == 0) {38        return true;39      }40    }41    return false;42  }43};

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem