Statement

Given an input string, word, return all possible permutations of the string.

Note: The order of permutations does not matter.

Constraints:

  • All characters in word are unique.

  • 1≤1 \leq word.length ≤6\leq 6

  • All characters in word are lowercase English letters.

Pattern: Subsets

Problems such as this one, where we need to find the combinations or permutations of a given string, are good examples to solve using the subsets pattern as it describes an efficient Depth-First Search (DFS) approach to handle all these problems.

Solution

Let’s discuss a few basics first. We know that n!n! is the number of permutations for a set of size nn. Another obvious and important concept is that if we choose an element for the first position, then the total permutations of the remaining elements are (n−1)!(n-1)!.

For example, if we’re given the string “abcd” and we pick “a” as our first element, then for the remaining elements we have the following permutations:

Similarly, if we pick “b” as the first element, permute “acd”, and prepend each permutation with “b”, we can observe a pattern here as shown in the illustration above. That pattern tells us how to find all remaining permutations for each character in the given string.

We can do this recursively to find all permutations of substrings, such as “bcd”, “acd”, and so on. This implies that generating all possible permutations of the given string involves exploring different combinations of characters, which can be done efficiently using the subset technique. The key idea is to take one character of the given string at a time and find all the permutations that start with this chosen character. For this, imagine filling empty positions equal to the length of the string in the following manner: place the chosen character at the first position, then against this character, try all the remaining characters in the second position. Next, for each pair of characters in the first and second positions, try all the remaining characters in the third position. Keep doing this until we reach the last position to be filled. This process will allow us to systematically arrange each character in different positions and generate all possible permutations of the given string.

Here is a visual representation of all recursions for input string “bad”:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

Let’s start with the simplest step—swapping the indexes of the input string. We create a function to swap ithi^{th} and jthj^{th} indexes of a given string.

class Permutations {
    // This function will swap characters for every permutation
    public static String swapChar(String word) {
        char[] swapIndex = word.toCharArray();
        char temp = swapIndex[0];
        swapIndex[0] = swapIndex[1];
        swapIndex[1] = temp;
        return new String(swapIndex);
    }
    // Driver code
    public static void main( String args[] ) {
        String[] inputWord = {"ab", "bad", "abcd"};
        for (int index = 0; index < inputWord.length; index++)
        {
            String permutedWords = swapChar(inputWord[index]);
            System.out.println(index + 1 + ".\t Input string: '" + inputWord[index] + "'");
            System.out.println("\t Swapping character at index 0 with index 1");
            System.out.println("\t Swapped indices: " + permutedWords);
            System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}
Permutations

The next part of the solution construction consists of actually calculating the first permutation for the input string. After swapping, we need to find the permutations as well. Let’s see how we can implement this logic.

We create a recursive function to compute the permutations of the string that has been passed as input. The function behaves in the following way:

  • We fix the first character of the input string and swap it with its immediate next character.

  • We swap the indexes and get a new permutation of the string, which is stored in the variable, swappedStr.

  • The recursive call for the function increments the index by adding 11 to the currentIndex variable to compute the next permutation.

  • All permutations of the string are stored in the result array, but for the following code snippet, only the base case—that is, only the first permutation—is displayed.

class Permutations {
 
    // This function will swap characters for every permutation
    public static String swapChar(String word,int i, int j) 
    {
        char[] swapIndex = word.toCharArray();
        char temp = swapIndex[i];
        swapIndex[i] = swapIndex[j];
        swapIndex[j] = temp;
        return new String(swapIndex);
    }
    public static void permuteStringRec(String word, int currentIndex, ArrayList<String> results)
    {
        // Prevents adding duplicate permutations
        if(currentIndex == 1)
        {
            results.add(word); 
            return;
        }
        for (int index = currentIndex; index < word.length(); index++)
        {
            // swaps character for each permutation
            String swappedStr = swapChar(word, currentIndex, index);
            System.out.println("\t After swapping the indices in the string: " + String.valueOf(swappedStr) + ", index: " + index);
            // recursively calls itself to find each permutation
            permuteStringRec(swappedStr, currentIndex + 1, results);
        }
    }
    // Driver code
    public static void main( String args[] ) {
        String[] inputWord = {"ab", "bad", "abcd"};
        ArrayList<String> results = new ArrayList<String>();
        for (int index = 0; index < inputWord.length; index++)
        {
            System.out.println(index + 1 + ".\t Input string: '" + inputWord[index] + "'");
            permuteStringRec(inputWord[index], 0, results);
            System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}
Permutations

We first swapped the indexes and then displayed the first possible permutation of the input string, that is, the input string itself. Let’s update the functionality to compute and store all possible permutations.

To implement this logic, we’ve made a function that takes the string as input, calls the recursive function, permuteStringRec that computes all permutations (as done in the previous step), and finally stores and displays the result array containing the permutations.

class Permutations {
 
    public static String swapChar(String word,int i, int j) 
    {
        char[] swapIndex = word.toCharArray();
        char temp = swapIndex[i];
        swapIndex[i] = swapIndex[j];
        swapIndex[j] = temp;
        return new String(swapIndex);
    }
    public static  void permuteStringRec(String word, int currentIndex, ArrayList<String> results)
    {
        // Prevents adding duplicate permutations
        if(currentIndex == word.length() - 1)
        {
            results.add(word);
            //System.out.println(Arrays.toString(results));
            return ;
        }
        for (int index = currentIndex; index < word.length(); index++)
         {
            // swaps character for each permutation
            String swappedStr = swapChar(word, currentIndex, index);
            // recursively calls itself to find each permutation
            permuteStringRec(swappedStr, currentIndex + 1, results);
         }
    }
    public static ArrayList<String> permuteWord(String word)
    {
        ArrayList<String> results = new ArrayList<String>();
        // Starts finding permuations from start of string
        permuteStringRec(word, 0, results);
        return results;
    }
    // Driver code
    public static void main( String args[] ) {
        String[] inputWord = {"ab", "bad", "abcd"};
        for (int index = 0; index < inputWord.length; index++)
        {
            ArrayList <String> permutedWords = permuteWord(inputWord[index]);
            System.out.println(index + 1 + ".\t Input string: '" + inputWord[index] + "'");
            System.out.println("\t All possible permutations are: " + permutedWords);
             System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}
Permutations

Just the code

Here’s the complete solution to this problem:

class Permutations {
 
    public static String swapChar(String word,int i, int j) 
    {
        char[] swapIndex = word.toCharArray();
        char temp = swapIndex[i];
        swapIndex[i] = swapIndex[j];
        swapIndex[j] = temp;
        return new String(swapIndex);
    }
    public static  void permuteStringRec(String word, int currentIndex, ArrayList<String> results)
    {
        if(currentIndex == word.length() - 1)
        {
            results.add(word);
            return ;
        }
        for (int index = currentIndex; index < word.length(); index++)
         {
            String swappedStr = swapChar(word, currentIndex, index);
            permuteStringRec(swappedStr, currentIndex + 1, results);
         }
    }
    public static ArrayList<String> permuteWord(String word)
    {
        ArrayList<String> results = new ArrayList<String>();
        permuteStringRec(word, 0, results);
        return results;
    }
    // Driver code
    public static void main( String args[] ) {
        String[] inputWord = {"ab", "bad", "abcd"};
        for (int index = 0; index < inputWord.length; index++)
        {
            ArrayList <String> permutedWords = permuteWord(inputWord[index]);
            System.out.println(index + 1 + ".\t Input string: '" + inputWord[index] + "'");
            System.out.println("\t All possible permutations are: " + permutedWords);
             System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}
Permutations

Solution summary

Let’s review what approach we’ve used to solve the problem above:

  1. Fix the first index and keep swapping the character at this index with the other characters of the string one by one.

  2. After each swap, skip the first character and recursively compute the permutation of the remaining string.

  3. Add the string to the result when the last character of the string is reached.

Time complexity

Let’s anaylze the time complexity of the solution code above:

  • permuteWord(): There are n!n! (factorial of nn) permutations of a string of length nn.
  • permuteStringRec(): This is a recursive function that generates these permutations. For a string of length nn, there are nn recursive calls at the first level, n−1n-1 calls for the second, and so on. This results in a total of n×(n−1)×(n−2)×⋯×1=n!n \times (n-1) \times (n-2) \times \dots \times 1 = n! calls.
  • swapChar(): The swap function has a time complexity of O(n)O(n) since it involves creating a list from the string and then joining it back into a string after the swap. This operation is done for each recursive call.

So, the overall time complexity of generating all permutations of a string of length nn is O(n×n!)O(n \times n!)

Space complexity

The space complexity of this solution is dependent on the depth of the recursive call stack. The maximum depth of recursion is nn, so the space complexity is O(n)O(n).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.