Find Whether Two Strings are Permutation of each other

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

Input: Two Strings

Output: True or false based on whether strings are permutation of other 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.

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

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

Complete Code for Both Methods:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class PermutationStrings {
public boolean isPermutation(String s1, String s2){
if(s1.length()!=s2.length()){
return false;
}
HashMap<Character, Integer> ht = new HashMap<>();
for(int i=0;i<s1.length();i++){
char c = s1.charAt(i);
if(ht.containsKey(c)){
int val = ht.get(c) + 1;
ht.put(c, val);
}else{
ht.put(c, 1);
}
}
for(int i=0;i<s2.length();i++){
char c = s2.charAt(i);
if(ht.containsKey(c)){
int val = (int)ht.get(c);
if(val==0){
return false;
}
val;
ht.put(c, val);
}else{
return false;
}
}
Set keys = ht.keySet();
Iterator<Character> iterator = keys.iterator();
while(iterator.hasNext()){
char c = iterator.next();
if(ht.get(c)!=0){
return false;
}
}
return true;
}
public static void main(String args[]){
String s1 = "sumit";
String s2 = "mtisu";
PermutationStrings p = new PermutationStrings();
System.out.println(s1 +" and "+ s2 + " are permutation of each other? " + p.isPermutation(s1, s2));
s1 = "xyzab";
s2 = "bayzxx";
System.out.println(s1 +" and "+ s2 + " are permutation of each other? " + p.isPermutation(s1, s2));
}
}

Output:

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