Description

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:

1Input: s1 = "ab", s2 = "eidbaooo"
2Output: true
3Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

1Input: s1 = "ab", s2 = "eidboaoo"
2Output: false

Constraints:

  • 1 <= s1.length, s2.length <= 10^4
  • s1 and s2 consist of lowercase English letters.

Solution

The problem requires us to check if permutations of s1 occurs in s2, not the other way.

Using Sorting

One way to solve this is to sort both the strings. Now, we know that we have to check sliding window of size s1.length() in the string s2. So, we create sliding window of size s1.length() from s2, sort elements of this substring and verify if those are exactly same as sorted s1.

1s1 = sorted s1
2for i = 0, i < s2.length - s1.length; i++ 
3    if s1 == sorted (s2[i, i + s1.length])
4        return true
5    return false

 1class Solution {
 2    public boolean checkInclusion (String s1, String s2) {
 3        if (s1.length() > s2.length())
 4            return false;
 5        String sortedS1 = sort(s1);
 6        String substringS2 = "";
 7        for (int i = 0; i <= s2.length() - s1.length(); i++) {
 8            substringS2 = sort(s2.substring(i, i + s1.length())); // This doesn't sace space
 9            if (sortedS1.equals(substringS2)) {
10                return true;
11            }
12        }
13        return false;
14    }
15
16    private String sort(String input) {
17        char[] chars = input.toCharArray();
18        Arrays.sort(chars);
19        return new String(chars);
20    }
21}
  • Time Complexity: O(n1 log n1) + (n2 - n1)(n1 log n1) where n1 = length of s1 and n2 = length of s2. This is because sorting of array s1 takes O(n1 log n1). Next we iterate for upto n2 - n1 times and each iteration requires sorting of substring which is of length n1.
  • Space Complexity: O(n1)

Using HashMap

The array s1 is permutation of substring of s2. If both of them have same characters for same frequency. So, we can use HashMap to track each character frequency. First we find out frequency of characters of s1. Next, we iterate through characters of s2 with each iteration considering window of length s1.length.

 1class Solution {
 2    public boolean checkInclusion (String s1, String s2) {
 3        if (s1.length() > s2.length())
 4            return false;
 5        Map<Character, Integer> s1Map = new HashMap<>();
 6
 7        // create map of s1
 8        for (char c : s1.toCharArray()) {
 9            s1Map.put(c, s1Map.getOrDefault(c, 0) + 1);
10        }
11        for (int left = 0; left <= s2.length() - s1.length(); left++) {
12            Map<Character, Integer> s2Map = new HashMap<>();
13
14            // create map of substring of s2
15            int right = left;
16            while (right < left + s1.length()) {
17                char c = s2.charAt(right);
18                s2Map.put(c, s2Map.getOrDefault(c, 0) + 1);
19                right++;
20            }
21            
22            // check both maps are equal
23            if (areMapEqual(s1Map, s2Map)) {
24                return true;
25            }
26        }
27        return false;
28    }
29
30    private boolean areMapEqual(Map<Character, Integer> map1, Map<Character, Integer> map2) {
31        for (char c : map1.keySet()) {
32            if (map1.get(c) != map2.getOrDefault(c, -1)) {
33                return false;
34            }
35        }
36        return true;
37    }
38}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Using Array to store frequency

Instead of using HashMap, we could also use array to store number of times each character occurs. Because the problem constraint states that each character is lowercase English alphabetic character, we have to allocate array of size 26.

 1class Solution {
 2    public boolean checkInclusion (String s1, String s2) {
 3        if (s1.length() > s2.length())
 4            return false;
 5        int[] s1Array = new int[ARRAY_SIZE];
 6
 7        // create map of s1
 8        for (char c : s1.toCharArray()) {
 9            s1Array[c - 'a']++;
10        }
11        for (int left = 0; left <= s2.length() - s1.length(); left++) {
12            int[] s2Array = new int[ARRAY_SIZE];
13
14            // create map of substring of s2
15            int right = left;
16            while (right < left + s1.length()) {
17                char c = s2.charAt(right);
18                s2Array[c - 'a'] = s2Array[c - 'a'] + 1;
19                right++;
20            }
21
22            // check both maps are equal
23            if (Arrays.equals(s1Array, s2Array)) {
24                return true;
25            }
26        }
27        return false;
28    }
29}
  • Time Complexity: O(n)
  • Space Complexity: O(1) because we allocate array of size 26.