Skip to content

How Generate All Possible Permutations String Python

Updated: at 02:12 AM

Permuting strings refers to generating all possible rearrangements of the characters in a given string. Finding every permutation of a string is a common technical interview question asked by companies like Google, Facebook, Amazon, etc. during coding interviews. Mastering this concept requires knowledge of recursion and backtracking algorithms. This how-to guide will provide a step-by-step walkthrough of solving the technical interview question - “Find All Permutations of a String” using Python.

Table of Contents

Open Table of Contents


Generating all permutations of a string involves rearranging the characters into every possible order. For example, the string “ABC” has the following 6 permutations:

["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]

The number of permutations of a string with unique characters is factorial of the length of the string. So a string of length n has n! permutations.

The permutations can be generated using a recursive backtracking algorithm that swaps each character of the string with every other character one by one and recursively calls itself with the rest of the string.


To follow this guide, you should have:

Step-by-Step Implementation

Follow these steps to generate all permutations of a given string in Python:

1. Create the Permute Function

We will create a permute() function that takes a string as input and returns a list of all permutations of that string.

def permute(s):

    # permutations list
    permutations = []

    # Base case
    if len(s) == 1:
        return [s]

        # For every character in string
        for i, char in enumerate(s):

            # Remove current char and find permutations of remaining chars
            remaining_chars = s[:i] + s[i+1:]

            # Recursive call
            subs = permute(remaining_chars)

            # Append current char to every permutation of remaining chars
            for p in subs:
                permutations.append(char + p)

    return permutations

2. Call the Function

To generate all permutations of a string, simply call the permute() function on the input string:

input = "ABC"

This will print all permutations of “ABC”:

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

We can also print each permutation on a new line for better visibility:

for p in permute(input):



3. Handle Duplicate Characters

The above implementation works for strings with unique characters. To handle duplicate characters, we need to skip permutations where the order of duplicate chars is same.

We can modify our code as:

def permute(s):
    permutations = []
    if len(s) == 1:
        return [s]

    char_set = set(s)
    for curr_char in char_set:
        new_s = s.replace(curr_char,'')
        subs = permute(new_s)

        for sub in subs:
            index_list = [i for i, x in enumerate(s) if x == curr_char]
            for index in index_list:
                p = sub[0:index] + curr_char + sub[index:]

    return permutations

Now this will print all permutations for a string with duplicates:



['AABC', 'AACB', 'ABAC', 'ABCA', 'ACAB', 'ACBA', 'BAAC', 'BACA', 'BCAA', 'CAAB', 'CABA', 'CBAA']

4. Improve Efficiency

The above brute force solution generates all n! permutations. This can be slow for longer strings.

We can optimize it using the following ideas:

a. Use Swapping

Instead of removing one char at a time, we can swap the current char with every other char in the string.

def permute(s):

    perms = []

    if len(s) <= 1:

        for i in range(len(s)):
            for j in range(i+1, len(s)):
                s_list = list(s)
                s_list[i], s_list[j] = s_list[j], s_list[i]

    return perms

b. Use Hash Table

We can store permutations in a hash table to avoid duplicates.

def permute(s):

    perms = []
    perm_dict = {}

    if len(s) <= 1:

        for i in range(len(s)):
            for j in range(i+1, len(s)):
                s_list = list(s)

                # Swap
                s_list[i], s_list[j] = s_list[j], s_list[i]

                perm = ''.join(s_list)

                # Skip duplicates
                if perm in perm_dict:

                perm_dict[perm] = True

    return perms

This skips already seen permutations, greatly improving efficiency.


Some key points:

With this comprehensive guide, you should be able to implement an efficient permutation algorithm in Python to ace your next coding interview!

Example Use Cases

Here are some examples of how string permutation algorithms are used in real-world applications:

1. Spell Checkers

Spell checkers like in word processors use permutations to generate suggestions for misspelled words. By permuting letters, they can find valid dictionary words that closely match the incorrect word.

2. Word Games

Games like Scrabble, Words with Friends, crossword puzzles use permutations to check if a player’s word is valid and score it appropriately.

3. Anagram Solvers

Finding all anagrams of a word means generating permutations of its letters. Anagram solvers use similar permutation algorithms.

4. Data Generation

Permuting identifying strings can be used to anonymize or generate test data for applications. Shuffling user emails, names can produce realistic test records.

5. Cryptography

Encryption algorithms like the Data Encryption Standard shuffle bits using techniques like permutation and substitution to securely encrypt data.


This guide provided a step-by-step walkthrough of solving the common technical interview coding challenge - generate all permutations of a given string in Python. We implemented a recursive backtracking solution, handled duplicate characters, optimized for efficiency using swapping and hash tables, analyzed time complexity, and covered real-world applications of string permutation algorithms. With diligent practice of questions like these, you will be fully prepared to demonstrate your Python skills and pass technical coding interviews at top technology companies.