The challenge

Given a word (a string of lowercase letters), return all its permutations in alphabetical order. Do not use built-in permutation functions.

Examples:

permutations("the");
// → [eht, eth, het, hte, teh, the]

permutations("a");
// → [a]

This puzzle is asked on Codewars and HackerRank Java tracks. Two parts trip people up: generating the permutations from scratch, and ordering them alphabetically.

Solution 1: recursive, no built-ins

The classic recursive approach. Each call removes one character, recurses on the rest, then prepends the removed character to every sub-result:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeSet;

public class Permutations {
    public static List<String> permutations(String s) {
        if (s.length() == 1) {
            List<String> base = new ArrayList<>();
            base.add(s);
            return base;
        }

        TreeSet<String> result = new TreeSet<>(); // sorted, dedup
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            String rest = s.substring(0, i) + s.substring(i + 1);
            for (String sub : permutations(rest)) {
                result.add(ch + sub);
            }
        }

        return new ArrayList<>(result);
    }
}

Why this works:

  1. Base case. A single character has only one permutation — itself.
  2. Recursive case. For each character, remove it from the string, recursively get all permutations of what is left, and prepend the removed character.
  3. TreeSet. A TreeSet<String> deduplicates (important for words like "hello" with repeated letters) and keeps natural alphabetical order.
  4. Final conversion. Return as List<String> — TreeSet already iterates in sorted order.

Solution 2: backtracking with sorted characters

Generates permutations directly in alphabetical order, no final sort needed:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutations {
    public static List<String> permutations(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars); // sorted input → sorted output
        List<String> result = new ArrayList<>();
        backtrack(new StringBuilder(), new String(chars), result);
        return result;
    }

    private static void backtrack(StringBuilder path, String remaining, List<String> result) {
        if (remaining.isEmpty()) {
            result.add(path.toString());
            return;
        }
        Set<Character> seen = new HashSet<>();
        for (int i = 0; i < remaining.length(); i++) {
            char ch = remaining.charAt(i);
            if (seen.contains(ch)) continue; // skip duplicate at this level
            seen.add(ch);
            path.append(ch);
            backtrack(path,
                      remaining.substring(0, i) + remaining.substring(i + 1),
                      result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

Why this works: Sorting the input characters means the for-loop tries them in alphabetical order at every depth, so the list grows already sorted. The seen set inside each level avoids duplicate permutations from repeated letters.

Solution 3: iterative with the next-permutation algorithm

Generates permutations one at a time using the same algorithm std::next_permutation uses in C++:

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

public class Permutations {
    public static List<String> permutations(String s) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        List<String> result = new ArrayList<>();
        result.add(new String(arr));
        while (nextPermutation(arr)) {
            result.add(new String(arr));
        }
        return result;
    }

    private static boolean nextPermutation(char[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] >= a[i + 1]) i--;
        if (i < 0) return false;
        int j = a.length - 1;
        while (a[j] <= a[i]) j--;
        char tmp = a[i]; a[i] = a[j]; a[j] = tmp;
        // reverse a[i+1..end]
        for (int l = i + 1, r = a.length - 1; l < r; l++, r--) {
            tmp = a[l]; a[l] = a[r]; a[r] = tmp;
        }
        return true;
    }
}

Why this works: nextPermutation mutates the array to the next lexicographic ordering. Starting from the sorted input, repeatedly calling it walks through every permutation in alphabetical order until it returns false. Constant extra memory beyond the result list.

Complexity

Solution Time Space
Recursive + TreeSet O(n! × n log n) O(n! × n)
Backtracking O(n! × n) O(n! × n)
next-permutation O(n! × n) O(n! × n)

n! is the number of permutations, n is the cost per string. For n = 10 that is 3.6 million strings — keep inputs short.

Test cases

import static org.junit.jupiter.api.Assertions.assertEquals;

assertEquals(List.of("a"), Permutations.permutations("a"));
assertEquals(List.of("ab", "ba"), Permutations.permutations("ab"));
assertEquals(6, Permutations.permutations("abc").size());
assertEquals(List.of("eht","eth","het","hte","teh","the"),
             Permutations.permutations("the"));
assertEquals(60, Permutations.permutations("hello").size()); // 5!/2! = 60 unique