How to Find All Permutations of a String in Java

Introduction

In this tutorial, we will learn how to find the permutation of a String in a Java Program. This is a fundamental programming concept that demonstrates the power of recursion and logical thinking. It’s a tricky question and is often asked in Java interviews to test problem-solving skills. String permutations are essential for solving algorithm-based problems and optimizing solutions. This concept is widely applied in generating combinations, solving puzzles, and understanding data arrangement patterns. The tutorial will cover step-by-step explanations to enhance understanding and practical implementation. With clear examples, you will confidently tackle similar challenges in coding interviews and projects.

Algorithm for Permutation of a String in Java

We will first take the first character from the String and permute it with the remaining characters.

For example, if String = "ABC":

• First character = A
• Remaining character permutations = BC and CB

Now we can insert the first character into the available positions in the permutations:

• BC -> ABC, BAC, BCA
• CB -> ACB, CAB, CBA

We can write a recursive function to return the permutations and then another function to insert the first characters to get the complete list of permutations.

Java Program to Print Permutations of a String

package com.journaldev.java.string;

import java.util.HashSet;
import java.util.Set;

/**
 * Java Program to find all permutations of a String
 * @author Pankaj
 *
 */
public class StringFindAllPermutations {
    public static Set<String> permutationFinder(String str) {
        Set<String> perm = new HashSet<String>();
        // Handling error scenarios
        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        char initial = str.charAt(0); // first character
        String rem = str.substring(1); // Full string without first character
        Set<String> words = permutationFinder(rem);
        for (String strNew : words) {
            for (int i = 0; i <= strNew.length(); i++) {
                perm.add(charInsert(strNew, initial, i));
            }
        }
        return perm;
    }

    public static String charInsert(String str, char c, int j) {
        String begin = str.substring(0, j);
        String end = str.substring(j);
        return begin + c + end;
    }

    public static void main(String[] args) {
        String s = "AAC";
        String s1 = "ABC";
        String s2 = "ABCD";
        System.out.println("\nPermutations for " + s + " are: \n" + permutationFinder(s));
        System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
        System.out.println("\nPermutations for " + s2 + " are: \n" + permutationFinder(s2));
    }
}

Output

Permutations for AAC are:

[AAC, ACA, CAA]

Permutations for ABC are:

[ACB, ABC, BCA, CBA, CAB, BAC]

Permutations for ABCD are:

[DABC, CADB, BCAD, DBAC, BACD, ABCD, ABDC, DCBA, ADBC, ADCB, CBDA, CBAD, DACB, ACBD, CDBA, CDAB, DCAB, ACDB, DBCA, BDAC, CABD, BADC, BCDA, BDCA]

Conclusion

I have used Set to store the string permutations, ensuring duplicates are removed automatically. This approach guarantees that the output contains unique permutations, making the results cleaner and more accurate. A Set is ideal for scenarios where data uniqueness is critical. It simplifies the process by handling duplicate elimination without requiring additional checks. Additionally, using a recursive function ensures all possible permutations are covered effectively. This method provides flexibility for handling strings of varying lengths. Understanding string permutations is essential for solving complex programming problems and preparing for coding interviews. That’s all for finding all permutations of a String in Java, complete with optimized solutions.