How will you print all permutations of characters in a string?
2026 Update: String Permutations — Three Approaches and the Duplicates Problem
Generating all permutations of a string is a classic recursion/backtracking problem. The real interview challenge is handling duplicates without generating repeated permutations.
from collections import Counter
from math import factorial
# Approach 1: Simple recursion (no duplicates in input)
def permute_simple(s: str) -> list:
if len(s) list:
result = []
def backtrack(start):
if start == len(chars):
result.append(''.join(chars))
return
for i in range(start, len(chars)):
chars[start], chars[i] = chars[i], chars[start]
backtrack(start + 1)
chars[start], chars[i] = chars[i], chars[start]
backtrack(0)
return result
# Approach 3: Handle duplicates — use a frequency counter
def permute_unique(s: str) -> list:
"""Generate all UNIQUE permutations (handles duplicates)."""
result = []
counter = Counter(s)
def backtrack(path: list):
if len(path) == len(s):
result.append(''.join(path))
return
for char in sorted(counter): # sorted for deterministic order
if counter[char] > 0:
path.append(char)
counter[char] -= 1
backtrack(path)
path.pop()
counter[char] += 1
backtrack([])
return result
# Count unique permutations without generating them
def count_unique_permutations(s: str) -> int:
"""n! / (c1! * c2! * ... ck!) where ci = count of each character."""
n = len(s)
counts = Counter(s)
denominator = 1
for c in counts.values():
denominator *= factorial(c)
return factorial(n) // denominator
# Test
print(permute_simple("abc")) # 6 permutations
print(permute_swap(list("abc"))) # 6 permutations
print(permute_unique("aab")) # ['aab', 'aba', 'baa'] — only 3, not 6
print(count_unique_permutations("aab")) # 3
print(count_unique_permutations("mississippi")) # 34650
Interview follow-ups:
- “Find all permutations that are palindromes” → only possible if at most one character has odd frequency
- “k-th permutation of a string” → O(n²) without generating all permutations; use factorial number system (LeetCode #60)
- “Next permutation” → LeetCode #31 — find next lexicographically greater arrangement in O(n)
- “Time complexity?” → O(n × n!) to generate all permutations (n! permutations, each takes O(n) to construct)
💡Strategies for Solving This Problem
The Backtracking Classic
Got this at Google. I spent 20 minutes trying to come up with a clever iterative solution before realizing: just use recursion. Sometimes the obvious answer is the right answer.
Core Insight
To generate all permutations of "ABC":
- Fix 'A', generate permutations of "BC" → ABC, ACB
- Fix 'B', generate permutations of "AC" → BAC, BCA
- Fix 'C', generate permutations of "AB" → CAB, CBA
This is recursion by definition. Each level fixes one character, recurses on the rest.
The Approach
Backtracking with Swap:
- For each position, try every remaining character
- Swap it to current position
- Recurse on remaining positions
- Swap back (backtrack)
This generates all n! permutations.
Alternative: Build String Character by Character
Instead of swapping, you can build permutations by choosing which character to add next. Easier to understand but uses more space.
Time Complexity
There are n! permutations, and generating each takes O(n) time to copy the string. Total: O(n × n!)
You can't do better - you have to generate all n! permutations.
My Interview Mistake
I tried to optimize to O(n!) by not copying strings. My interviewer asked "How will you return the results?" Right - you have to copy them. Sometimes you can't optimize.