Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Permutations of a String in Java: Swap, Restore and Remove Duplicates

Generate sorted unique string permutations using your swap-and-backtrack approach, with per-position duplicate handling and an honest sorting cost.

MediumRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Return every unique permutation of a lowercase string, sorted lexicographically. A permutation uses all character copies but rearranges their positions. It is not a substring, subsequence or subset.

The supplied task permits 1–8 lowercase letters and explicitly includes repeated characters. Practice with GFG’s distinct string permutations. aab has three distinct answers, not six duplicated strings.

Constraints & requirements

CONTRACT
Original task: 1–8 lowercase letters. Fix one position with swaps, use a fresh per-position set, restore each swap, then sort the results.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    s="abc"
    Output
    [abc,acb,bac,bca,cab,cba]

    All three positions are arranged; this is not a subsequence task.

  2. Example 2 Case 2

    Input
    s="aab"
    Output
    [aab,aba,baa]

    The two a positions must not duplicate identical strings.

  3. Example 3 Case 3

    Input
    s="aa"
    Output
    [aa]

    Equal letters give one distinct arrangement.

Solve on GeeksforGeeks ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Fix the current position, then arrange the remaining suffix.

02Hint 2

Try each distinct character only once at this position.

03Hint 3

Undo swaps; sort at the end because swap traversal is not dictionary order.

How to think before coding

Index means the next position to FIX. Try swapping each remaining distinct character into that position. A new local set belongs to that one level, because the same letter may still be needed at later positions. Recurse to index+1 and swap back on return. Save a new String at the leaf, then sort outputs because swap traversal is not automatically lexicographic.

Brute force and the improvement

Permute the original character positions in all n! orders, then deduplicate full strings in a set and sort them. Building candidates costs O(n·n!), even when many equal letters make the strings identical. The working permutation takes O(n) space, while retained unique strings take O(P·n), plus sorting workspace, for P distinct outputs. Move duplicate prevention into each recursive level: try each distinct next CHARACTER once. This avoids exploring interchangeable copies before they create duplicate full answers.

Intuition: fix one position at a time

For abc, decide which character belongs at position 0. Swap that character into place, recursively arrange positions 1 onward, then swap back. The recursion can trust that the earlier positions are fixed for its branch.

Your base/Permutation.java implements this idea for distinct characters. To meet the requested problem, add a fresh tried set at each position. It prevents two identical letters from starting equivalent sibling branches. It must not be global: the second a still has to appear later in aab.

Swap order also does not guarantee sorted answers. With three distinct letters, the final branch can produce cba before cab. Sort the finished strings instead of claiming the traversal is already dictionary order.

Algorithm

  1. Convert the input to a character array.
  2. At index, try each distinct character from the unfixed suffix.
  3. Swap it into index and recurse on index+1.
  4. Swap back after the child returns.
  5. At the end, save a new String snapshot.
  6. Sort the completed strings lexicographically.

Java solution

Each level uses a fresh duplicate set, then swaps, recurses and restores. Sorting the final result is necessary because swap traversal is not automatically lexicographic.

Java
import java.util.*;

class Solution {
    public static List<String> permuteString(String s) {
        List<String> result = new ArrayList<>();
        permuteChars(s.toCharArray(), 0, result); // Work on a mutable copy, not the original String.
        Collections.sort(result); // Swap traversal is NOT automatically lexicographic.
        return result;
    }
    private static void permuteChars(char[] chars, int index, List<String> result) {
        if (index == chars.length) { // Every position is fixed on this branch.
            result.add(new String(chars)); // Snapshot before swaps restore the shared array.
            return;
        }
        Set<Character> tried = new HashSet<>(); // A fresh set for this position, not the whole search.
        for (int i = index; i < chars.length; i++) {
            if (!tried.add(chars[i])) continue; // Equal letters would create the same sibling branch.
            swapChars(chars, index, i); // Fix this candidate in the current position.
            permuteChars(chars, index + 1, result); // Arrange the remaining suffix.
            swapChars(chars, index, i); // Restore the suffix before another candidate is tried.
        }
    }
    private static void swapChars(char[] chars, int i, int j) {
        char saved = chars[i]; chars[i] = chars[j]; chars[j] = saved; // Exchange, including i == j.
    }

    public static void main(String[] args) {
        System.out.println(permuteString("aab")); // [aab, aba, baa]
    }
}

The default invocation returns [aab, aba, baa]. Strings saved from the array are independent snapshots, so later swaps cannot change them.

Recursion tree and dry run

Numbered illustrated dry run for Permutations of a String; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: s = "aab"

What to track: chars is a shared array. index marks the first unfixed position. Each frame has a fresh tried set; swap back restores the exact caller state.

  1. Fix the first a

    Java operationswapChars(chars, index, i);
    Stateindex = 0; i = 0; chars = aab; tried = {a}

    Swapping a position with itself is harmless. The child fixes index 1.

  2. Reach the first leaf

    Java operationresult.add(new String(chars));
    Statechoices a, a, b reach index = 3; result = ["aab"]

    new String captures the arrangement before any swap-back changes the shared array.

  3. Try the other suffix order

    Java operationswapChars(chars, index, i);
    Stateback at index = 1, i = 2: aab becomes aba; leaf saves "aba"

    The earlier child has returned and been restored. Fixing b at index 1 leaves a for the final position.

  4. Skip an equal root choice

    Java operationif (!tried.add(chars[i])) continue;
    Staterestored root chars = aab; i = 1 contains a already in root tried

    Starting with the second a would generate the same first-letter branch, so no recursive child is created.

  5. Start with b

    Java operationpermuteChars(chars, index + 1, result);
    Stateroot i = 2 swaps to baa; the suffix produces one leaf "baa"

    At the suffix, its fresh tried set skips the second equal a. The root set must not be reused at this depth.

  6. Restore, then order the output

    Java operationCollections.sort(result);
    Stateall swaps restored; result = ["aab","aba","baa"]

    Sorting makes the required display order explicit; swap traversal alone does not guarantee it.

Final result: ["aab","aba","baa"] after sorting.

Worked example · read from top to bottom
fix position 0 in aab
├─ choose a
│  ├─ fix position 1 with a → aab
│  └─ fix position 1 with b → aba
├─ second a at position 0 → skip equal sibling
└─ choose b
   └─ suffix aa has one distinct arrangement → baa

After generating aba, swapping position 1 back restores the parent’s array to aab. After the b-root branch returns, its root swap is also restored. Each call undoes only its own swap, which is why nested choices do not leak into siblings.

Why it works

At depth index, the prefix consists of the chosen fixed characters and the suffix contains every remaining copy. Swapping preserves character frequencies. Trying every distinct next letter covers every possible next character once; the recursive suffix completes every distinct arrangement below it. A leaf uses the whole array, and sorting changes only answer order.

Complexity and alternative approaches

With N characters and U distinct permutations, snapshotting costs O(N·U). A conservative generation bound is O(N²·U), counting up to N scanned suffix candidates at each node; the familiar all-distinct bound is O(N·N!). Sorting adds O(N·U log U) worst-case character-comparison work.

Auxiliary storage is O(N²) in the worst case for the live per-level tried sets, plus O(N) array/stack; output is O(N·U). A frequency-array DFS branches by letter type and naturally produces dictionary order when scanning letters ascending, avoiding final sorting and per-position sets.

Generating N! positional permutations and deduplicating afterward works for small inputs but does avoidable repeated work. The total unique count is N! / ∏frequency(letter)!.

Common mistakes

  • Omitting the restore swap corrupts future branches.
  • A global used-letter set prevents legitimate repeated letters in one word.
  • Claiming sorted traversal when swap candidates follow array order.
  • Returning only a count when the question asks for the actual strings.

Practice next

Next lessonPalindrome Permutation II

Back to Recursion and backtracking →