Find all permutations of a String

Given a string, find all the permutations of the string.
For example:
Input String: abc
Output: {bca, acb, abc, cba, bac, cab}


Question Asked in

Google, Amazon, Facebook, Adobe, AppNexus


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




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.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




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!)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer