String Permutations

Problem Statement

Given a string, return all possible permutations of its characters.

Example: Input: "abc" → Output: ["abc","acb","bac","bca","cab","cba"]

Approach 1: Backtracking / Recursive Swapping

Explanation: Swap each character with all subsequent characters and recurse.

Time Complexity: O(n! × n) (permutation count × copy time)

Space Complexity: O(n) (recursion stack)

function permute(s, l):
    if l == len(s):
        add s to result
        return
    for i in l..len(s)-1:
        swap s[l] and s[i]
        permute(s, l+1)
        swap back
permute(string, 0)

💡 Think: Swap each character with all positions ahead and recurse to generate permutations.

Approach 2: Using Used Array

Explanation: Build permutation step by step, marking characters used.

Time Complexity: O(n! × n)

Space Complexity: O(n)

function backtrack(path, used):
    if len(path) == n:
        add path copy to result
        return
    for i in 0..n-1:
        if used[i]:
            continue
        used[i]=True
        backtrack(path + s[i], used)
        used[i]=False
backtrack("", [False]*n)

💡 Think: Track used characters in a boolean list and build permutations step by step.

Approach 3: Itertools / Library (Python)

Explanation: Use built-in permutation function.

Time Complexity: O(n! × n)

Space Complexity: O(n! × n)

from itertools import permutations
result = list(permutations(s))

💡 Think: Use Python’s itertools.permutations to generate all permutations directly.

Solve on LeetCode