Find all permutations of a String

Algorithm/Insights

1. We use a hash set to store all permutations of the string.
2. If string is null or of 0 length, we return a hashset with "" as element
3. We keep first character of the string and recursively call getAllPermutations on the remaining string.
4. When the function returns, we add the first character to all positions in all the strings that we got in the hashset.
Please see algorithm visualization to test the algorithm with sample data.

Code Snippet

			
package com.ideserve.questions.saurabh;

import java.util.HashSet;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a string, find all the permutations of the string.
 * For example:
 * Input String: abc
 * Output: {bca, acb, abc, cba, bac, cab}
 *
 * @author Saurabh
 */
public class AllPermutationsString {
	
	public static HashSet<String> getAllPermutations(String str) {
		// Create a hash set to prevent any duplicate entries
		HashSet<String> permutations = new HashSet<String>();
		
		if(str == null || str.length() == 0) {
			permutations.add("");
			return permutations;
		}
		
		char first = str.charAt(0);
		String remainingString = str.substring(1);
		HashSet<String> words = getAllPermutations(remainingString);
		for(String word: words) {
			for(int i = 0; i <= word.length(); i++) {
				String prefix = word.substring(0, i);
				String suffix = word.substring(i);
				permutations.add(prefix + first + suffix);
			}
		}
		return permutations;
	}
	
	public static void main(String[] args) {
		String str = "abc";
		HashSet<String> permutations = getAllPermutations(str);
		System.out.println(permutations.toString());
	}
}
		

Order of the Algorithm

Time Complexity is O(n*n!)