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:
Algorithm
The simplest method is to generate all the permutations of the short string and to check if the generated permutation is a substring of the longer string.
In order to generate all the possible pairings, we make use of a function permute(string_1, string_2, current_index). This function creates all the possible permutations of the short string .
To do so, permute takes the index of the current element as one of the arguments. Then, it swaps the current element with every other element in the array, lying towards its right, so as to generate a new ordering of the array elements. After the swapping has been done, it makes another call to permute but this time with the index of the next element in the array. While returning back, we reverse the swapping done in the current function call.
Thus, when we reach the end of the array, a new ordering of the array's elements is generated. The following animation depicts the process of generating the permutations.
!?!../Documents/561_Array.json:1000,563!?!
Complexity Analysis
Time complexity : . We match all the permutations of the short string , of length , with . Here, refers to the length of .
Space complexity : . The depth of the recursion tree is ( refers to the length of the short string ). Every node of the recursion tree contains a string of max. length .
Algorithm
The idea behind this approach is that one string will be a permutation of another string only if both of them contain the same characters the same number of times. One string is a permutation of other string only if .
In order to check this, we can sort the two strings and compare them. We sort the short string and all the substrings of , sort them and compare them with the sorted string. If the two match completely, 's permutation is a substring of , otherwise not.
Complexity Analysis
Time complexity : . where is the length of string and is the length of string .
Space complexity : . array is used .
Algorithm
As discussed above, one string will be a permutation of another string only if both of them contain the same charaters with the same frequency. We can consider every possible substring in the long string of the same length as that of and check the frequency of occurence of the characters appearing in the two. If the frequencies of every letter match exactly, then only 's permutation can be a substring of .
In order to implement this approach, instead of sorting and then comparing the elements for equality, we make use of a hashmap which stores the frequency of occurence of all the characters in the short string . We consider every possible substring of of the same length as that of , find its corresponding hashmap as well, namely . Thus, the substrings considered can be viewed as a window of length as that of iterating over . If the two hashmaps obtained are identical for any such window, we can conclude that 's permutation is a substring of , otherwise not.
Complexity Analysis
Time complexity : . hashmap contains atmost 26 keys. where is the length of string and is the length of string .
Space complexity : . hashmap contains atmost 26 key-value pairs.
Algorithm
Instead of making use of a special HashMap datastructure just to store the frequency of occurence of characters, we can use a simpler array data structure to store the frequencies. Given strings contains only lowercase alphabets ('a' to 'z'). So we need to take an array of size 26.The rest of the process remains the same as the last approach.
Complexity Analysis
Time complexity : , where is the length of string and is the length of string .
Space complexity : . and of size 26 is used.
Algorithm
Instead of generating the hashmap afresh for every window considered in , we can create the hashmap just once for the first window in . Then, later on when we slide the window, we know that we add one preceding character and add a new succeeding character to the new window considered. Thus, we can update the hashmap by just updating the indices associated with those two characters only. Again, for every updated hashmap, we compare all the elements of the hashmap for equality to get the required result.
Complexity Analysis
Time complexity : , where is the length of string and is the length of string .
Space complexity : . Constant space is used.
Algorithm
The last approach can be optimized, if instead of comparing all the elements of the hashmaps for every updated corresponding to every window of considered, we keep a track of the number of elements which were already matching in the earlier hashmap and update just the count of matching elements when we shift the window towards the right.
To do so, we maintain a variable, which stores the number of characters(out of the 26 alphabets), which have the same frequency of occurence in and the current window in . When we slide the window, if the deduction of the last element and the addition of the new element leads to a new frequency match of any of the characters, we increment the by 1. If not, we keep the intact. But, if a character whose frequency was the same earlier(prior to addition and removal) is added, it now leads to a frequency mismatch which is taken into account by decrementing the same variable. If, after the shifting of the window, the evaluates to 26, it means all the characters match in frequency totally. So, we return a True in that case immediately.
Complexity Analysis
Time complexity : . where is the length of string and is the length of string .
Space complexity : . Constant space is used.
Analysis written by: @vinod23