Java Program to Find all Permutations of String

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (176K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

Introduction

A permutation of a string is a rearrangement of its characters. For example, the permutations of the string "ABC" are "ABC", "ACB", "BAC", "BCA", "CAB", and "CBA". In this guide, we will create a Java program to find and display all possible permutations of a given string.

Problem Statement

Create a Java program that:

• Takes a string as input.
• Finds all the permutations of that string.
• Displays each permutation.

Example 1:

• Input: "ABC"
• Output: ABC, ACB, BAC, BCA, CAB, CBA

Example 2:

• Input: "AB"
• Output: AB, BA

Solution Steps

1. Prompt for Input: Use the Scanner class to read a string input from the user.
2. Create a Recursive Method: Use a recursive method to generate all permutations of the string.
3. Display Each Permutation: Print each permutation as it is generated.

Java Program

import java.util.Scanner; /** * Java Program to Find All Permutations of a String * Author: https://www.javaguides.net/ */ public class StringPermutations { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // Step 1: Prompt the user for input System.out.print("Enter a string to find its permutations: "); String input = scanner.nextLine(); // Step 2: Generate and display permutations System.out.println("Permutations of the string are:"); findPermutations(input, ""); } // Step 3: Recursive method to find permutations public static void findPermutations(String str, String prefix) { if (str.isEmpty()) { // Base case: If the string is empty, print the prefix System.out.println(prefix); } else { for (int i = 0; i < str.length(); i++) { // Choose the character at index i char ch = str.charAt(i); // Form the remaining string after removing the character at index i String remaining = str.substring(0, i) + str.substring(i + 1); // Recurse with the remaining string and the prefix updated with the chosen character findPermutations(remaining, prefix + ch); } } } } 

Explanation

Step 1: Prompt for Input

• The program uses the Scanner class to read a string input from the user. This string will be used to generate permutations.

Step 2: Generate and Display Permutations

• The program calls the findPermutations method, passing the input string and an empty string as the initial prefix.

Step 3: Recursive Method to Find Permutations

• Base Case: If the string str is empty, the current permutation (held in prefix) is printed.
• Recursive Case:
  • The method loops through each character in the string.
  • For each character, it creates a new string by removing the current character from the original string.
  • The method then recursively calls itself with the new string (remaining) and the updated prefix (which includes the current character).

Key Points:

• The base case ensures that when the string becomes empty, the accumulated prefix (which is a complete permutation) is printed.
• The recursive case systematically explores all possible permutations by choosing each character in turn and recursing on the remaining characters.

Output Examples

Example 1:

Enter a string to find its permutations: ABC Permutations of the string are: ABC ACB BAC BCA CAB CBA 

Example 2:

Enter a string to find its permutations: AB Permutations of the string are: AB BA 

Conclusion

This Java program efficiently finds and displays all permutations of a given string using recursion. The recursive approach is well-suited for this task as it naturally breaks down the problem into smaller subproblems. This method is both elegant and powerful, making it a common choice for generating permutations in programming.