How to Generate All Permutations of a String in Kotlin — Fast O(n) Approach (Handles Duplicates + Large Input Tips)
When most developers search for “Generate All Permutations of a String”, they find solutions that work but are often slow, overly complex, or hard to read.
Today, we’re going to cut through the noise and build a simple, fast, and easy-to-understand Kotlin solution that runs in O(n) time per permutation — which is as efficient as it gets.
We’ll cover:
- What permutations actually are
- Why naive solutions are slow
- The O(n) approach using in-place swapping
- Clean Kotlin code with full explanation
What Is a String Permutation?
A permutation is simply a different arrangement of the same characters.
For example, the string "ABC" has these permutations:
ABC, ACB, BAC, BCA, CAB, CBAIf a string has n unique characters, there are exactly n! permutations.
e.g 4!=4×3×2×1=24
That means 3 characters → 6 permutations, 4 characters → 24 permutations, and so on.
Why We Need an O(n) Approach
Many beginner solutions to generate all permutations of a string use recursion with string concatenation. That works, but it creates a lot of unnecessary string objects in memory — making it slow for larger strings.
We can do better by:
- Avoiding extra strings (working on a mutable list of characters instead)
- Swapping in-place to generate permutations
- Recursing efficiently without repeated slicing or copying
This gives us O(n) work per permutation instead of heavier O(n²) string-building overhead.
The In-Place Swapping Algorithm
Here’s the idea:
- Convert the string into a mutable character array.
- Recursively swap the current index with each possible next character.
- When we reach the end, print or store the permutation.
- Swap back to restore the original state (backtracking).
By doing swaps in-place, we avoid creating new arrays or strings at each step.
Kotlin Implementation
fun generateUniquePermutations(str: String) {
val chars = str.toCharArray().sortedArray() // Sort to group duplicates
permuteUnique(chars, 0)
}
private fun permuteUnique(chars: CharArray, index: Int) {
if (index == chars.size - 1) {
println(String(chars))
return
}
val seen = mutableSetOf<Char>()
for (i in index until chars.size) {
if (chars[i] in seen) continue // Skip duplicate characters
seen.add(chars[i])
swap(chars, index, i) // Place chosen char at 'index'
permuteUnique(chars, index + 1) // Recurse
swap(chars, index, i) // Backtrack
}
}
private fun swap(chars: CharArray, i: Int, j: Int) {
val temp = chars[i]
chars[i] = chars[j]
chars[j] = temp
}
fun main() {
generateUniquePermutations("AAB")
}How This Code Works
Let’s break it down:
generatePermutations
- Converts the input string to a
CharArrayso we can modify it directly. - Starts recursion from the first index.
permute
- Base case: If
indexis at the last character, we’ve found a full permutation, so we print it. - Loop: Swap the current index with every possible position (including itself).
- Recursion: Move to the next index and repeat.
- Backtrack: Swap back so the next iteration starts with the original order.
swap
- Simple character swap using a temporary variable.
- Works in constant time O(1).
Time Complexity
This program generates all permutations of a given string.
If the string length is n:
- The number of permutations =
n!
For each permutation, the code does:
- A series of swaps (O(1) each)
- Recursive calls that together visit all permutations.
The total work is proportional to n × n! because:
- At each permutation, you spend O(n) to print the result (constructing
String(chars)is O(n)). - The recursive structure ensures we visit all
n!permutations.
So:
T(n)=O(n×n!)
Space Complexity
There are two aspects:
Auxiliary space (call stack):
- The recursion depth is
n(one frame for each index position). - Each frame holds constant space aside from parameters and local variables.
- So the recursion stack = O(n).
Extra storage:
- You store the characters in a
CharArray(sizen). - No extra big data structures are used.
- Output printing doesn’t count toward auxiliary space complexity (it’s external).
Thus:
S(n)=O(n)
(excluding the space needed for the output itself).
Why This Is O(n) Per Permutation
Each recursive level only requires:
- One swap (O(1))
- One swap back (O(1))
- A constant amount of work for printing or storing
That’s O(n) for each permutation generated, which is optimal — you can’t generate n! permutations faster than that.
Benefits of This Approach
Fast — avoids extra string copies
Memory efficient — works in-place
Readable — short and clear code
Scalable — handles larger strings without choking your CPU
Output
Running generatePermutations("ABC") gives:
ABC
ACB
BAC
BCA
CBA
CABExactly all possible permutations — no duplicates, no missing ones.
Handling Duplicate Characters
Without extra care, "AAB" will produce duplicate outputs.
To fix this:
- Sort the characters first so duplicates are adjacent.
- At each recursion level, use a
Set<Char>to skip duplicates.
Kotlin Implementation (Fast + Duplicate-Safe)
fun generateUniquePermutations(str: String) {
val chars = str.toCharArray().sortedArray() // Sort to group duplicates
permuteUnique(chars, 0)
}
private fun permuteUnique(chars: CharArray, index: Int) {
if (index == chars.size - 1) {
println(String(chars))
return
}
val seen = mutableSetOf<Char>()
for (i in index until chars.size) {
if (chars[i] in seen) continue // Skip duplicate characters
seen.add(chars[i])
swap(chars, index, i) // Place chosen char at 'index'
permuteUnique(chars, index + 1) // Recurse
swap(chars, index, i) // Backtrack
}
}
private fun swap(chars: CharArray, i: Int, j: Int) {
val temp = chars[i]
chars[i] = chars[j]
chars[j] = temp
}
fun main() {
generateUniquePermutations("AAB")
}For "AAB", output is:
AAB
ABA
BAA— unique, no duplicates.
Wait, what if we used all 26 characters? Hmm… actually, let’s just go with 25.
There are a few limitations we need to talk about.
Limitations & Large Input Handling
Even with an O(n) per permutation algorithm, the total permutations grow as n! (factorial).
For "ABCDEFGHIJKLMNOPQRSTUWXYZ" (25 characters):
25!≈1.55×10²⁵ permutations
This number is so huge that:
- You can’t generate all permutations in your lifetime.
- You can’t store them — it would require trillions of terabytes.
- Even printing them will eventually cause
OutOfMemoryErrorin the JVM because the output stream andStringBuildercan’t keep up.
How to Avoid Crashes for Large Strings
- Generate Lazily (Streaming)
Use Kotlin sequences to yield one permutation at a time:
fun permutationsSequence(chars: CharArray, index: Int = 0): Sequence<String> = sequence {
if (index == chars.size - 1) {
yield(String(chars))
} else {
for (i in index until chars.size) {
swap(chars, index, i)
yieldAll(permutationsSequence(chars, index + 1))
swap(chars, index, i)
}
}
}With this, you process each permutation immediately, instead of storing them.
2. Limit Output
If you just need the first k permutations:
var count = 0
val maxCount = 1000
for (p in permutationsSequence("ABCDEFGHIJKLMNOP".toCharArray())) {
println(p)
if (++count >= maxCount) break
}3. Use Next-Permutation Algorithm
Instead of generating all permutations at once, generate only the next one on demand — useful for lexicographic iteration without memory blow-up.
Why This Approach Stands Out
O(n) time per permutation — optimal.
Memory-friendly with in-place swaps.
Duplicate-safe.
Large input advice so you don’t crash your program.
Conslusion
If you need to generate all permutations of a string in Kotlin, the in-place swapping method is your best friend for performance and readability. But remember — factorial growth is unavoidable, so for very large strings, think streaming, limiting, or on-demand generation instead of trying to produce everything at once.
With this, you’ve got a production-ready, safe, and scalable solution for permutations in Kotlin.
