Cracking The Coding Interview Together – Problem 8.8: Permutations with Dups

Picture this: You are building a custom feature for a password generation utility or a word game solver. Your system needs to generate all possible distinct arrangements of a given input string. Sounds straightforward, right? You pull out your favorite textbook permutation algorithm, run it against a string like "AAB", and suddenly your output list contains duplicate entries like "ABA", "ABA", "BAA". If you push this straight to production, your downstream components bloat, memory consumption spikes, and your caching layer breaks down due to redundant keys. Today, we are going to tackle this head-on as we explore how to generate permutations when our input contains duplicate characters.

Problem Statement

We need to write a method that computes all unique permutations of a string whose characters are not necessarily unique. The resulting list must not contain any duplicate permutations. Our operational goals are clear: correctness, efficiency, and minimal memory overhead by avoiding brute-force deduplication sets where possible.

Analyze the Problem Together

When we look at standard permutations for unique characters (like "ABC"), we typically fix a character at the current index and recursively permute the remaining substring. However, when duplicates enter the picture, blind swapping leads to redundant branches in our recursion tree.

Let's compare our options:

The "Aha!" moment here is shifting our perspective from swapping indices to building strings using available character counts. By counting the frequency of each character upfront, we can drive our backtracking choice points by unique keys rather than arbitrary positions. If we have two 'A's, we can choose 'A' twice, but we make that choice from a shared pool of available inventory.

Questions for the Interviewer

Before we write a single line of code, let's establish best practices by asking clarifying questions:

• "What is the expected character set? Are we dealing with ASCII, standard UTF-8, or strictly lowercase English letters?"
• "Should the output list be returned in any particular lexicographical order?"
• "What is the maximum length of the input string we need to support within memory limits?"

Think About the Solution

Our architecture for this solution relies on a frequency map. We map each character to its remaining count. Our recursive method takes the current built string (or a StringBuilder for performance), the remaining counts map, and the target length. At each step in our recursion, we iterate through the unique keys in our map. If a character's count is greater than zero, we decrement its count, append it to our builder, recurse, and then backtrack by restoring the count and removing the character from our builder.

Write Code and Explain

Here is our production-ready Java implementation:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PermutationsWithDups {

    public static List<String> printPerms(String s) {
        List<String> result = new ArrayList<>();
        if (s == null) {
            return result;
        }
        
        // Step 1: Build frequency map
        Map<Character, Integer> map = buildFreqMap(s);
        
        // Step 2: Kick off backtracking
        printPerms(map, "", s.length(), result);
        return result;
    }

    private static Map<Character, Integer> buildFreqMap(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        return map;
    }

    private static void printPerms(Map<Character, Integer> map, String prefix, int remaining, List<String> result) {
        // Base case: permutation is complete
        if (remaining == 0) {
            result.add(prefix);
            return;
        }

        // Try each available unique character
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            char c = entry.getKey();
            int count = entry.getValue();

            if (count > 0) {
                // Choose
                map.put(c, count - 1);
                // Explore
                printPerms(map, prefix + c, remaining - 1, result);
                // Un-choose (Backtrack)
                map.put(c, count);
            }
        }
    }

    public static void main(String[] args) {
        String input = "AAB";
        List<String> permutations = printPerms(input);
        System.out.println(permutations);
    }
}

Let's walk through this step by step:

1. buildFreqMap tallies up every character. For "AAB", our map looks like {'A': 2, 'B': 1}.

2. In our recursive method, we iterate over map entries. When we pick 'A', we decrement its count to 1, append it to our prefix, and recurse with remaining = 2.

3. Once remaining hits zero, we capture the valid permutation and unwind our stack, safely restoring the map state for the next branch.

Time & Space Complexity

Let's analyze the resource utilization:

• Time Complexity: $\mathcal{O}(\frac{N!}{n_1! n_2! \dots n_k!})$ where $N$ is the total length of the string and $n_i$ is the frequency of each duplicate character. This is the exact number of unique permutations possible, meaning our algorithm wastes zero cycles on duplicate branches.
• Space Complexity: $\mathcal{O}(N)$ for the recursion stack depth and the frequency map storage, plus the memory required to store the final output list.

Why This Problem Matters (The Senior Perspective)

Algorithms like this teach us the value of problem modeling. Beginners often default to post-processing solutions—generating all permutations and filtering them through a HashSet. In high-throughput distributed systems, that naive approach introduces massive memory pressure and unnecessary CPU cycles. By pruning duplicate branches at the source using frequency constraints, we build robust, scalable services that perform predictably under heavy loads.

Final Thoughts

Mastering recursion with state restoration is a hallmark of strong engineering fundamentals. Take this code, experiment with larger inputs, and try optimizing string concatenation with a StringBuilder. Happy coding, and we will see you in the next breakdown!