**Objective** – Given a string, find the number of distinct permutations or anagrams of that string.

**Example**:

String x = "abc" Output: 6 (abc, acb, bac, bca, cab, cba) String x = "aab" Output: 3 (aab, aba, baa)

**Approach**:

- Number of ways to arrange n distinct items are = n!.
- If we have duplicate items, say one item repeated m1 times, then we need to divide n! by m1!. Since these items can be arranged in m1! ways but that will not produce any different results.
- For example let’s say we have 6 items {a, b, a, c, d, c}, we have ‘a’ which is occurring twice. So in one of the permutation – ‘aabccd’ . if we replace ‘a’ at 0
^{th}index and ‘a’ at 1^{st}index, it will not produce any different result. ‘aa’ can be arranged in !2 ways. Same with ‘c’ So our final result will be 6!/(2!*2!).

Let’s drive a generic formula –

**Implementation**:

- Count all the characters in the given string, say its N.
- Calculate N!, this might be our final result if none of the characters are repeated.
- Count the occurrences of all the characters, store it. We are using Hash Map in our implementation below.
- Find the factorial of all the counts and divide the result by these factorials. (Non repeated characters will have count 1 and 1! = 1 so dividing by 1 will not affect our final result.)

**Code**:

import java.util.HashMap; | |

import java.util.Iterator; | |

import java.util.Set; | |

public class DistinctPermutations { | |

public static void permutations(String input){ | |

//covert string to char array | |

char[] chars = input.toCharArray(); | |

//create a HashMap | |

HashMap<Character, Integer> map = new HashMap<>(); | |

for (int i = 0; i <chars.length ; i++) { | |

char x = chars[i]; | |

if(map.containsKey(x)){ | |

int count = map.get(x); | |

count++; | |

map.put(x, count); | |

}else | |

map.put(x, 1); | |

} | |

int result = factorial(chars.length); | |

//handle duplicates, divide the result by all the counts factorial in the hash map | |

Set set = map.keySet(); | |

Iterator<Character> iterator = set.iterator(); | |

while (iterator.hasNext()){ | |

char key = iterator.next(); | |

int count = map.get(key); | |

//divide the result by count | |

int factorialCount = factorial(count); | |

result = result/factorialCount; | |

} | |

System.out.println("Number of distinct permutations of String: '" + input + "' are: " + result); | |

} | |

public static int factorial(int num){ | |

if(num==0) | |

return 1; | |

int result = 1; | |

for (int i = 2; i <=num ; i++) { | |

result *= i; | |

} | |

return result; | |

} | |

public static void main(String[] args) { | |

String input = "abc"; | |

permutations(input); | |

input = "aabc"; | |

permutations(input); | |

input = "aabccd"; | |

permutations(input); | |

} | |

} |

**Output**:

Number of distinct permutations of String: 'abc' are: 6 Number of distinct permutations of String: 'aabc' are: 12 Number of distinct permutations of String: 'aabccd' are: 180

**Read Next Article** : Print All The Permutations Of a String