Java - Permutations of a String
Problem Statement
Given a string S, print all possible permutations of the characters in the string.
Example 1:
Input: "ABC"
Output:
ABC
ACB
BAC
BCA
CAB
CBA
Example 2:
Input: "AB"
Output:
AB
BA
Approach: Backtracking (Recursive Method)
The idea is to swap characters at different positions recursively and generate all possible orderings.
Algorithm
Base Case: If l == r (left index equals right index), print the permutation.
Recursive Step:
Swap the current character with every other character.
Recur with l + 1 (next index).
Swap back (backtracking) to restore the original order.
Java Code Implementation
public class StringPermutations {
// Function to generate permutations
private static void permute(String str, int l, int r) {
if (l == r) {
System.out.println(str); // Print the permutation
} else {
for (int i = l; i <= r; i++) {
str = swap(str, l, i); // Swap characters
permute(str, l + 1, r); // Recur for next index
str = swap(str, l, i); // Backtrack (restore original order)
}
}
}
// Swap function to swap characters at positions i and j
private 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);
}
// Main function to test
public static void main(String[] args) {
String str = "ABC";
System.out.println("All permutations of " + str + " are:");
permute(str, 0, str.length() - 1);
}
}
Output
All permutations of ABC are:
ABC
ACB
BAC
BCA
CAB
CBA
Complexity Analysis
Step Time Complexity
Generating permutations O(N!) (Factorial growth)
Swapping O(N)
Total Complexity O(N × N!)
Approach: Using Collections (Efficient for Large Strings)
Instead of modifying the string, use a character list.
Java Code
import java.util.*;
public class StringPermutationsList {
// Function to generate permutations
private static void permute(List<Character> chars, int l, int r) {
if (l == r) {
System.out.println(chars);
} else {
for (int i = l; i <= r; i++) {
Collections.swap(chars, l, i); // Swap
permute(chars, l + 1, r); // Recur
Collections.swap(chars, l, i); // Backtrack
}
}
}
// Main function to test
public static void main(String[] args) {
String str = "ABC";
List<Character> charList = new ArrayList<>();
for (char c : str.toCharArray()) charList.add(c);
System.out.println("All permutations of " + str + " are:");
permute(charList, 0, str.length() - 1);
}
}
Approach: Using next_permutation() from Java Streams
Java 8+ provides an easier way of using Lexicographic order.
Java Code
import java.util.Arrays;
public class StringPermutationsLex {
public static void main(String[] args) {
String str = "ABC";
char[] chars = str.toCharArray();
Arrays.sort(chars); // Sort to start with lexicographically smallest
do {
System.out.println(new String(chars));
} while (nextPermutation(chars));
}
private static boolean nextPermutation(char[] array) {
int i = array.length - 2;
while (i >= 0 && array[i] >= array[i + 1]) i--;
if (i == -1) return false;
int j = array.length - 1;
while (array[j] <= array[i]) j--;
char temp = array[i];
array[i] = array[j];
array[j] = temp;
Arrays.sort(array, i + 1, array.length);
return true;
}
}
