Check Permutation Two Strings

Written by:Fatih KABAKCI

The question is to check if one of the permutation of the strings has already another one in given two strings. Brute force of the solution of this problem would take O(n2 * n!) since there is a calculation of all possible permutations of strings. Therefore, we should not go over this solution. There should be a better implementation of this !

There are only two strings need to be compared to see if one of them is a permutation version of another. What if we would check only frequency of the characters as long as they are same length strings ? In order to do this, we need to know each character how many times they appear. Then, basically two character sets will involve each other by checking their frequencies if they are same or not. First, we have to make sure that if the size of strings are not equal, so we won't have to continue the algorithm, we will just return false because all permutations have to be same length versions.

We could use different type of data structures to solve this problem. We will use Map objects here.

O(n) Solution

Mark each character how many times they appear and store in a map. Then, iterate through the map, and compare all of them match. The solution have been provided in below.

package com.fatihkabakci.arrStr;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * 
 * @author fkabakci
 * Given two strings, determine if one of them is permutation of the other.
 * O(n) solution
 * 
 * abc -- cba -- true
 * abc -- dac -- false
 */
public class CheckPermutation {
	private static Map<Character, Integer> getMap(String str) {
		Map<Character, Integer> m = new HashMap<Character, Integer>();
		for(char key : str.toCharArray()) {
			if(m.containsKey(key))
				m.put(key, m.get(key) + 1);
			else
				m.put(key, 1);
		}
		return m;
	}
	public static boolean checkPermutation(String strA, String strB) {
		if(strA.length() != strB.length())
			return false;
		
		Map<Character, Integer> mapA = getMap(strA);
		Map<Character, Integer> mapB = getMap(strB);
		
		for(Entry<Character, Integer> e : mapA.entrySet()) {
			if(mapB.get(e.getKey()) == null || e.getValue() != mapB.get(e.getKey()))
				return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
		System.out.println(checkPermutation("abc", "abc"));
	}
}