Generate Permutations

Problem Statement

Given a string s, generate all possible permutations of the string.

A permutation is an arrangement of all or part of a set of objects, with regard to the order of the arrangement.

Examples

Example 1:

Input: s = "abc"
Output: ["abc", "acb", "bac", "bca", "cab", "cba"]

Example 2:

Input: s = "ab"
Output: ["ab", "ba"]

Constraints

• 1 <= s.length <= 6
• s consists of lowercase English letters only

Approach 1: Backtracking with Swap

Algorithm

Use backtracking to generate permutations by swapping characters at different positions.

Steps:

1. Start with the original string
2. For each position, swap with all remaining positions
3. Recursively generate permutations for the remaining positions
4. Backtrack by swapping back to restore original state

Implementation

Python:

def generate_permutations(s):
    """
    Generate all permutations using backtracking with swap
    Time: O(n!*n)
    Space: O(n!*n)
    """
    result = []
    chars = list(s)
    
    def backtrack(start):
        if start == len(chars):
            result.append(''.join(chars))
            return
        
        for i in range(start, len(chars)):
            # Swap characters
            chars[start], chars[i] = chars[i], chars[start]
            # Recursively generate permutations
            backtrack(start + 1)
            # Backtrack
            chars[start], chars[i] = chars[i], chars[start]
    
    backtrack(0)
    return result

Java:

class Solution {
    public List<String> generatePermutations(String s) {
        List<String> result = new ArrayList<>();
        char[] chars = s.toCharArray();
        
        backtrack(chars, 0, result);
        return result;
    }
    
    private void backtrack(char[] chars, int start, List<String> result) {
        if (start == chars.length) {
            result.add(new String(chars));
            return;
        }
        
        for (int i = start; i < chars.length; i++) {
            swap(chars, start, i);
            backtrack(chars, start + 1, result);
            swap(chars, start, i);
        }
    }
    
    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) where n is the length of the string
• Space Complexity: O(n!*n) for storing all permutations

Key Insights

1. Backtracking: Use backtracking to explore all possible arrangements
2. Swap Approach: Swap characters to generate different permutations
3. Permutation Count: For a string of length n, there are n! permutations
4. Recursion Base Case: When we’ve used all characters, we have a complete permutation

Edge Cases

1. Single character: String with one character
2. Two characters: Minimum case with two characters
3. All same characters: String with repeated characters
4. Maximum length: Handle the constraint limit of 6 characters

Test Cases

# Test cases
assert generate_permutations("abc") == ["abc", "acb", "bac", "bca", "cab", "cba"]
assert generate_permutations("ab") == ["ab", "ba"]
assert generate_permutations("a") == ["a"]
assert len(generate_permutations("abcd")) == 24  # 4! = 24

Follow-up Questions

1. Next Permutation: Find the next lexicographically greater permutation
2. Permutation Sequence: Find the kth permutation in lexicographic order
3. Permutations with Duplicates: Handle strings with duplicate characters
4. Permutation in String: Check if one string is a permutation of another

Common Mistakes

1. Incomplete backtracking: Not properly restoring state after recursion
2. Index errors: Going out of bounds in character arrays
3. Duplicate handling: Not handling duplicate characters correctly
4. Base case: Incorrect termination condition

Interview Tips

1. Start with examples: Walk through the permutation generation process
2. Explain backtracking: Show how the recursive approach works
3. Handle edge cases: Always consider single character and duplicate cases
4. Discuss complexity: Explain why it’s O(n!*n) time complexity
5. Trace through algorithm: Show how backtracking works step by step