String Permutations Program in Java

In this post, you will learn the String permutations program in Java. Generating permutations of a string involves finding all possible arrangements of its characters. Here’s a Java program to generate and print all permutations of a given string along with an explanation of the code:

package com.javacodepoint.string;

public class StringPermutations {

	public static void generatePermutations(String str, int left, int right) {
		if (left == right) {
			System.out.println(str);
			return;
		}

		for (int i = left; i <= right; i++) {
			str = swap(str, left, i); // Swap characters at positions 'left' and 'i'
			generatePermutations(str, left + 1, right); // Recur for remaining characters
			str = swap(str, left, i); // Backtrack by swapping back
		}
	}

	public static String swap(String str, int i, int j) {
		char[] charArray = str.toCharArray();
		char temp = charArray[i];
		charArray[i] = charArray[j];
		charArray[j] = temp;
		return String.valueOf(charArray);
	}

	public static void main(String[] args) {
		String input = "ABC";
		System.out.println("Permutations of '" + input + "':");
		generatePermutations(input, 0, input.length() - 1);
	}
}

OUTPUT:

Permutations of ‘ABC’:
ABC
ACB
BAC
BCA
CBA
CAB

Explanation:

1. The main method initializes the input string input with the value "abc". This is the string for which permutations will be generated.
2. The generatePermutations method is the main recursive function that generates permutations. It takes four arguments: the input string str, the current left index left, and the current right index right.
3. When left becomes equal to right, it means we have reached the end of a permutation, and the method prints the string.
4. The for loop runs from left to right, and for each iteration, it performs the following:
   • Swaps the characters at positions left and i using the swap method.
   • Recursively calls generatePermutations for the remaining characters by incrementing the left index.
   • Backtracks by swapping the characters back to the original order after the recursive call.
5. The swap method takes a string str and two indices i and j, swaps the characters at those positions, and returns the modified string.

See also: Maximum Occurring Character in a String | Compare two Strings