StringProblem 11 of 43
Print all the permutations of the given string
Problem Statement
Given a string, print all permutations of the string. A permutation is a rearrangement of all characters in the string.
Example:
-
Input:
"abc" -
Output:
["abc", "acb", "bac", "bca", "cab", "cba"] -
Input:
"ab" -
Output:
["ab", "ba"]
Note: A string of length n has n! permutations.
Approach 1: Recursion with Swapping
Intuition
Fix one character at a time and recursively permute the rest. Swap the current character with each subsequent character to generate all permutations.
Algorithm
- Start with index 0
- Swap current index with each index from current to end
- Recurse for the next index
- Backtrack by swapping back
java
import java.util.*;
public class Solution {
public List<String> getPermutations(String s) {
List<String> result = new ArrayList<>();
permute(s.toCharArray(), 0, result);
return result;
}
private void permute(char[] chars, int index, List<String> result) {
// Base case: reached end of string
if (index == chars.length) {
result.add(new String(chars));
return;
}
// Try swapping current position with each subsequent position
for (int i = index; i < chars.length; i++) {
swap(chars, index, i); // Swap
permute(chars, index + 1, result); // Recurse
swap(chars, index, i); // Backtrack
}
}
private void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}Complexity Analysis
- Time Complexity: O(n! × n) - n! permutations, each taking O(n) to construct
- Space Complexity: O(n) - Recursion stack depth
Approach 2: Using Visited Array
Intuition
Build permutations character by character. Use a visited array to track which characters have been used in the current permutation.
Algorithm
- For each position in the result, try each unused character
- Mark the character as used and recurse
- Backtrack by unmarking the character
java
import java.util.*;
public class Solution {
public List<String> getPermutations(String s) {
List<String> result = new ArrayList<>();
boolean[] visited = new boolean[s.length()];
permute(s, "", visited, result);
return result;
}
private void permute(String s, String current, boolean[] visited,
List<String> result) {
if (current.length() == s.length()) {
result.add(current);
return;
}
for (int i = 0; i < s.length(); i++) {
if (!visited[i]) {
visited[i] = true;
permute(s, current + s.charAt(i), visited, result);
visited[i] = false;
}
}
}
}Complexity Analysis
- Time Complexity: O(n! × n)
- Space Complexity: O(n) - Visited array + recursion stack
Approach 3: Handling Duplicates
Intuition
When the string has duplicate characters, some permutations will be repeated. To avoid duplicates:
- Sort the string first
- Skip a character if it's the same as the previous one and the previous one hasn't been used in the current path
java
import java.util.*;
public class Solution {
public List<String> getUniquePermutations(String s) {
List<String> result = new ArrayList<>();
char[] chars = s.toCharArray();
Arrays.sort(chars);
boolean[] visited = new boolean[chars.length];
permuteUnique(chars, "", visited, result);
return result;
}
private void permuteUnique(char[] chars, String current, boolean[] visited,
List<String> result) {
if (current.length() == chars.length) {
result.add(current);
return;
}
for (int i = 0; i < chars.length; i++) {
if (visited[i]) continue;
// Skip duplicates
if (i > 0 && chars[i] == chars[i-1] && !visited[i-1]) continue;
visited[i] = true;
permuteUnique(chars, current + chars[i], visited, result);
visited[i] = false;
}
}
}Complexity Analysis
- Time Complexity: O(n! × n) in worst case (all unique characters)
- Space Complexity: O(n)
Approach 4: Next Permutation (Iterative)
Intuition
Generate permutations in lexicographic order using the next permutation algorithm. This approach doesn't use recursion.
Key Takeaways
- n! permutations exist for a string of length n
- Swapping approach is most common and efficient for unique characters
- Visited array approach is cleaner but uses extra space
- For duplicates, sort first and skip repeated characters
- Next permutation provides an iterative solution
- Time complexity is unavoidably O(n!) since output is factorial
- This is a classic backtracking problem
- The swapping technique maintains the original order of untouched elements