This post is completed by 2 users

  • 1
 Add to List
Beginner

23. Find Whether Two Strings are Permutation of each other

Objective: Given Two Strings, check whether one string is a permutation of other

Input: Two Strings
Output: True or false based on whether strings are permutations of others or not.

Example: 

"sumit" and "tiums" are permutations of each other.
"abcd" and bdea" are not permutations of each other.

Approach:


Method 1: Time Complexity - O(nlgn)

Sort both the strings and compare it.

Output: 

sumit and mtisu are permutation of each other? true
xyzab and bayzxx are permutation of each other? false

Method 2 : Using Hash Map- Time Complexity - O(n)

  1. Check if both Strings are having the same length, if not, return false.
  2. Create a Hash Map, make character as key and its count as value
  3. Navigate the string one taking each character at a time
  4. check if that character already exists in a hash map, if yes then increase its count by 1, and if it doesn't exist insert it into a hash map with the count as 1.
  5. Now navigate the second string taking each character at a time
  6. check if that character exists in the hash map, if yes then decrease its count by 1 and if it doesn't exist then return false.
  7. At the end navigate through the hash map and check if all the keys have 0 count against it if yes then return true else return false.

Output: 
sumit and mtisu are permutation of each other? true
xyzab and bayzxx are permutation of each other? false

Related Problems: