Permutation In String

• Check for Base Case i.e if Length of str1 > Length of str2, return false.As substring length is always greater than or equal to permutation never small.
• Generate all the permutations of the short string and then check for each permutation if this string is present as a substring of the second string or not.
• Initialize a global boolean value named flag.
• To generate all the permutations of the small string, we make use of generatePermutation(flag, str1, str2, index).
• Steps involved in the previous function :
  • The index denotes the current index of the element in a small string.
  • Swap the current element with every other element in the string towards its right, so as to generate permutations.
  • Recursive call to generatePermutation (flag, str1, str2, index + 1).
  • While backtracking, revert the swapping done in the previous function call.

• Check for Base Case i.e if Length of str1 > Length of str2, return false.
• The idea behind the approach is that one string is a permutation of another string iff both strings contain the same characters and same frequencies.
• We sort both the strings so that all same characters are adjacent to each other.
• Sort the short string str1 and all permutations of the string str2 . Compare each and every permutation of str2. If they match completely, then return true else return false.

Check for Base Case i.e if Length of str1 > Length of str2, return false.

One string will be a permutation of another string only if both of them contain the same characters with the same frequency. Consider every possible substring in the long string str2 of the same length as that of string str1 and check the frequency of occurrence of the characters appearing in the two.If frequencies of every letter match exactly, then only str1’s permutation will be the substring of str2.

The steps involved are as follows :

• Build the HashMap named map1 which contains  key-value pair, where key = character of str1, and value =  frequency of key in str1.
• While ( i ≤  Length(str2) - Length(str1) )
• Build the HashMap named map2 which contains a key-value pair.
• While( j < Length(str1) )
  • map2 contains key = Character at (i + j) th index of str2

          If map1 equals map2

    Return True

• Return False

• Check for Base Case i.e if Length of str1 > Length of str2, return false.
• Make two vectors named vec1 and vec2, where vec1 contains frequencies of every letter in str1, and vec2 contains frequencies of every character in str2.
• Generate vector just once for the first window in str2.
• Slide the window, remove one preceding character, and add a new succeeding character to the new window.
• Update the vector by just updating the indices associated with those two characters only.
• Compare all the keys of every updated vector vec2 with the keys of vec1.

• By updating in approach 4, instead of comparing all the elements of the vectors i.e vec1 and vec2.
• For every updated vec2 corresponding to every window of str2 considered, keep a track of the number of elements that were already matching in the earlier vector and update just the count of matching elements when we shift the window towards the right.
• Initialize a variable count that represents the number of characters having the same frequency in str1 and the current window in str2.
• Update the count i.e increment by one when deduction of the last element in window and addition of new element in window leads to a new frequency.
• Update the count i.e. decrement by one when a character’s frequency is the same before addition or removal to the window.
• After sliding of the window is done, if count equals 26 i.e. all characters match exactly the same, return true.