Cracking The Coding Interview Together – Problem 8.7: Permutations without Dups

Have you ever stared at a combinatorial problem and felt that sinking realization that your nested loops are scaling catastrophically? When we design systems that process permutations—whether we are generating routing configurations, analyzing state transitions, or evaluating password combinations—the sheer volume of output data can bring an application to its knees if we aren't careful. Today, we are tackling a classic algorithmic challenge that tests our mastery of recursion and state management: computing all permutations of a string with unique characters.

Let's roll up our sleeves and explore how to build a clean, efficient, and robust solution together.

Problem Statement

Our objective for today is defined clearly in Chapter 8 of Cracking the Coding Interview (Problem 8.7): Write a method to compute all permutations of a string of unique characters. Assume that all characters in the string are distinct.

Let's define our operational goals:

• Input: A string S of length n consisting of unique characters.
• Output: A collection containing all possible permutations of the characters in S.
• Constraints: The total number of permutations will be n! (n factorial), so our memory and runtime footprints must account for this factorial growth.

Analyze the Problem Together

When we first look at this problem, our intuition might push us toward iterative approaches involving nested loops. But think about it: if the length of the string is dynamic—say, anywhere from 1 to 10 characters—how many nested loops would we need? Exactly, a dynamic number of loops screams for recursion.

Let's look at the "Aha!" conflict here. If we want to find all permutations of the string "abc", we can break it down into smaller sub-problems. What if we take the last character, 'c', and insert it into every possible position of all permutations of the remaining substring "ab"? The permutations of "ab" are "ab" and "ba". Inserting 'c' into all positions of "ab" yields "cab", "acb", and "abc". Inserting 'c' into all positions of "ba" yields "cba", "bca", and "bac".

Alternatively, we can use a backtracking approach where we build permutations character by character, keeping track of which characters have been used in the current path. Both approaches are valid, but building by insertion or swapping elements gives us profound insights into state transformation.

Questions for the Interviewer

Before we write a single line of code, as senior engineers, we must clarify the boundaries and expectations with our interviewer:

• "What is the maximum expected length of the input string? Since permutations scale at O(n!), do we need to worry about memory limits for large inputs?"
• "Should the output be returned in a specific sorted order, or is any arbitrary order acceptable?"
• "Can we assume the input string contains strictly unique characters as stated, or should our method validate for duplicates?"

Think About the Solution

Let's architect our solution using a classic recursive backtracking approach via character insertion. We will design a helper function that takes a remaining string to process and builds the permutations dynamically.

High-level architectural components:

• Base Case: When the remaining string is empty, we return a list containing an empty string, representing the termination of a valid path.
• Recursive Step: Remove the first character from the string, recursively compute permutations of the remaining substring, and then iterate through each returned permutation to insert our removed character at every possible index.
• Edge Cases: Null or empty input strings should return an appropriate collection (e.g., an empty list or a list containing an empty string depending on strict definitions).

Write Code and Explain

Here is our production-ready Java implementation. We have thoroughly documented every block so you can trace the execution flow easily.

import java.util.ArrayList;
import java.util.List;

public class PermutationGenerator {

    /**
     * Computes all permutations of a string containing unique characters.
     *
     * @param str the input string with unique characters
     * @return a list containing all permutations of the string
     */
    public static List<String> getPermutations(String str) {
        List<String> results = new ArrayList<>();
        
        // Handle edge cases cleanly
        if (str == null) {
            return results;
        }
        
        // Base case: if the string is empty, return a list with an empty string
        if (str.length() == 0) {
            results.add("");
            return results;
        }

        // Extract the first character and the remainder of the string
        char firstChar = str.charAt(0);
        String remainder = str.substring(1);
        
        // Recursively get permutations of the remaining substring
        List<String> words = getPermutations(remainder);
        
        // Insert the first character into every possible position of each sub-permutation
        for (String word : words) {
            for (int i = 0; i <= word.length(); i++) {
                String inserted = insertCharAt(word, firstChar, i);
                results.add(inserted);
            }
        }
        
        return results;
    }

    /**
     * Helper method to insert a character into a string at a specified index.
     */
    private static String insertCharAt(String word, char c, int i) {
        String start = word.substring(0, i);
        String end = word.substring(i);
        return start + c + end;
    }

    public static void main(String[] args) {
        String testStr = "abc";
        List<String> perms = getPermutations(testStr);
        System.out.println("Permutations of " + testStr + ": " + perms);
    }
}

Step-by-Step Walkthrough:

1. We check if the input string is null. If it is, we return an empty list immediately.
2. Our base case catches when str.length() == 0, returning a list containing an empty string so that subsequent insertions have a foundational building block.
3. We split the string into firstChar and remainder. We call getPermutations(remainder), diving down the call stack until we hit our base case.
4. As the recursion unwinds, we take each returned permutation string and loop through every possible insertion index from 0 to word.length().
5. The helper method insertCharAt slices the string and injects our character, populating our cumulative results list.

Time & Space Complexity

Let's analyze the algorithmic cost so we can reason about scale in production environments.

• Time Complexity: O(n! * n)
  There are n! total permutations for a string of length n. For each permutation, creating substrings and performing concatenation takes O(n) operations. Thus, the total time complexity scales factorially with respect to the input length.
• Space Complexity: O(n! * n)
  The memory footprint is dominated by storing all n! generated permutations, each of length n, inside our results list. Additionally, the call stack depth is bounded by O(n), but the memory allocated for output storage dictates our primary space constraint.

Why This Problem Matters (The Senior Perspective)

Combinatorial generation problems like permutations appear deceptively simple, but they serve as the foundational building blocks for critical real-world engineering tasks. Whether you are building test-case generation engines, solving constraint satisfaction problems (like Sudoku solvers or scheduling engines), or optimizing routing algorithms in logistics platforms, understanding how to systematically explore state spaces is non-negotiable.

In production systems, generating n! items in memory will quickly trigger OutOfMemoryError exceptions if n grows beyond 10 or 12. As senior engineers, we must recognize when to switch from storing all results in memory to utilizing lazy evaluation, Java Streams, or generator patterns that yield permutations on the fly. Furthermore, always validate your input constraints before triggering deep recursive call stacks to protect your application threads from stack overflow vulnerabilities.

Final Thoughts

Recursive backtracking and state combination are powerful tools in your engineering toolkit. By breaking a complex string manipulation problem down into smaller inductive steps, we transformed an intimidating combinatorial puzzle into clean, manageable code.

Take some time to experiment with this code: try refactoring the solution to use an in-place swapping approach with character arrays to optimize memory allocation. Keep practicing, keep building, and happy coding!