Permutations of string

Slug: permutations-of-string--123809

Difficulty: Basic

Id: 881785

Topic Tags: STL

Company Tags: None

Summary

Given a string, generate all possible permutations of the given string. This problem involves using the concept of permutation and recursion to solve it.

Detailed Explanation

To solve this problem, we can use the concept of recursion where we fix one character at a time and recursively call the function for the remaining characters.

Here's the step-by-step breakdown:

Start by initializing an empty vector result to store the permutations.
Define a recursive function permute that takes a string str and a character c as input.
In the permute function, iterate through the string and fix one character at a time.
For each fixed character, recursively call the permute function with the remaining characters (i.e., str without the fixed character).
After fixing all characters, add the permutation to the result vector.
Finally, return the result vector containing all possible permutations of the input string.

Here's a diagram illustrating the recursive approach:

str: "abc"
result = []
permute(str):
    fix 'a' and recursively call permute("bc")
    fix 'b' and recursively call permute("ac")
    fix 'c' and recursively call permute("ab")

Time Complexity: O(n!), where n is the length of the input string.
Space Complexity: O(n!), as we need to store all permutations in the `result` vector.

Optimized Solutions

Java

import java.util.*; public class Permutations { public static List<String> permute(String str) { List<String> result = new ArrayList<>(); permute(str.toCharArray(), 0, str.length() - 1, result); return result; } private static void permute(char[] arr, int l, int r, List<String> result) { if (l == r) { result.add(new String(arr)); } else { for (int i = l; i <= r; i++) { arr = swap(arr, l, i); permute(arr, l + 1, r, result); arr = swap(arr, l, i); } } } private static char[] swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } }