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, CBA

If 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:

1. Convert the string into a mutable character array.
2. Recursively swap the current index with each possible next character.
3. When we reach the end, print or store the permutation.
4. 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 CharArray so we can modify it directly.
• Starts recursion from the first index.

permute

• Base case: If index is 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 (size n).
• 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
CAB

Exactly 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 OutOfMemoryError in the JVM because the output stream and StringBuilder can’t keep up.

How to Avoid Crashes for Large Strings

1. 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.