All Permutations of a String 3 in Lexicographic Order

Problem

Given a string s with distinct or duplicate characters, print or return all permutations of s in lexicographic (sorted) order.

Examples

Example 1

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

Solution

Method 1 — Next-permutation (iterative)

Intuition

The next_permutation algorithm transforms the current permutation into the next larger permutation in lexicographic order. Starting from the characters sorted in non-decreasing order, repeatedly applying next_permutation enumerates all permutations in increasing lexicographic order until no next permutation exists.

Approach

• Sort s (so the first permutation is the smallest lexicographically).
• Print or collect the current permutation.
• While next_permutation succeeds, move to and collect the next permutation.

This is simple, efficient, and uses O(1) additional space (beyond output and the string) if a language provides next_permutation (C++). For languages without a standard helper, implement the next-permutation algorithm: find pivot, swap with successor, reverse suffix.

Code

C++

class Solution {
public:
  vector<string> permute(string s) {
    vector<string> ans;
    sort(s.begin(), s.end());
    do {
      ans.push_back(s);
    } while (next_permutation(s.begin(), s.end()));
    return ans;
  }
};

Go

package main

import "sort"

type Solution struct{}

func (Solution) Permute(s string) []string {
  arr := []rune(s)
  sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] })
  var ans []string
  ans = append(ans, string(arr))
  for nextPermutationRunes(arr) {
    ans = append(ans, string(arr))
  }
  return ans
}

func nextPermutationRunes(a []rune) bool {
  n := len(a)
  i := n - 2
  for i >= 0 && a[i] >= a[i+1] { i-- }
  if i < 0 { return false }
  j := n - 1
  for a[j] <= a[i] { j-- }
  a[i], a[j] = a[j], a[i]
  for l, r := i+1, n-1; l < r; l, r = l+1, r-1 { a[l], a[r] = a[r], a[l] }
  return true
}

Java

import java.util.*;

class Solution {
  public List<String> permute(String s) {
    List<String> ans = new ArrayList<>();
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    ans.add(new String(arr));
    while (nextPermutation(arr)) {
      ans.add(new String(arr));
    }
    return ans;
  }

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

  private void reverse(char[] a, int l, int r) {
    while (l < r) { char t = a[l]; a[l++] = a[r]; a[r--] = t; }
  }
}

Kotlin

class Solution {
  fun permute(s: String): List<String> {
    val arr = s.toCharArray().apply { sort() }
    val ans = mutableListOf<String>()
    ans.add(String(arr))
    while (nextPermutation(arr)) ans.add(String(arr))
    return ans
  }

  private fun nextPermutation(a: CharArray): Boolean {
    var i = a.size - 2
    while (i >= 0 && a[i] >= a[i+1]) i--
    if (i < 0) return false
    var j = a.size - 1
    while (a[j] <= a[i]) j--
    val t = a[i]; a[i] = a[j]; a[j] = t
    a.reverse(i+1, a.size)
    return true
  }
}

Python

class Solution:
  def permute(self, s: str) -> list[str]:
    arr = sorted(list(s))
    ans: list[str] = []
    ans.append(''.join(arr))
    while self._next_permutation(arr):
      ans.append(''.join(arr))
    return ans

  def _next_permutation(self, a: list[str]) -> bool:
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i+1]:
      i -= 1
    if i < 0:
      return False
    j = len(a) - 1
    while a[j] <= a[i]:
      j -= 1
    a[i], a[j] = a[j], a[i]
    a[i+1:] = reversed(a[i+1:])
    return True

Rust

pub struct Solution;
impl Solution {
  pub fn permute(s: String) -> Vec<String> {
    let mut arr: Vec<char> = s.chars().collect();
    arr.sort();
    let mut ans = Vec::new();
    ans.push(arr.iter().collect());
    while Self::next_permutation(&mut arr) {
      ans.push(arr.iter().collect());
    }
    ans
  }

  fn next_permutation(a: &mut Vec<char>) -> bool {
    let n = a.len();
    if n < 2 { return false }
    let mut i = n - 2;
    while i > 0 && a[i] >= a[i+1] { i -= 1; }
    if i == 0 && a[0] >= a[1] { return false }
    let mut j = n - 1;
    while a[j] <= a[i] { j -= 1; }
    a.swap(i, j);
    a[i+1..].reverse();
    true
  }
}

TypeScript

export class Solution {
  permute(s: string): string[] {
    const arr = s.split('').sort();
    const n = arr.length;
    const ans: string[] = [];
    ans.push(arr.join(''));
    while (this.nextPermutation(arr)) ans.push(arr.join(''));
    return ans;
  }

  private nextPermutation(a: string[]): boolean {
    let i = a.length - 2;
    while (i >= 0 && a[i] >= a[i+1]) i--;
    if (i < 0) return false;
    let j = a.length - 1;
    while (a[j] <= a[i]) j--;
    [a[i], a[j]] = [a[j], a[i]];
    let l = i+1, r = a.length-1;
    while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; }
    return true;
  }
}

Complexity

• ⏰ Time complexity: O(n * P) where P is the number of permutations (worst-case P = n!). Each transition to the next permutation takes O(n) in the worst case (for the suffix reversal).
• 🧺 Space complexity: O(n + P*n) including output; O(n) auxiliary for in-place operations.

Method 2 — Sort + deterministic backtracking (lexicographic DFS)

Intuition

If the input is sorted and the backtracking chooses characters in increasing index order while skipping used indices, the generated permutations follow lexicographic order. This is the sorted-skip backtracking pattern: sort first, then backtrack with a used array and the duplicate-skip condition.

Approach

• Sort s into arr.
• Use used[] to mark chosen positions.
• At each level iterate i from 0 to n-1, skipping used indices and skipping i when i>0 && arr[i]==arr[i-1] && !used[i-1].
• Append when cur.length == n.

Code

C++

class Solution2 {
public:
  vector<string> permute(string s) {
    int n = s.size();
    vector<string> ans;
    if (n == 0) return ans;
    sort(s.begin(), s.end());
    string cur; cur.reserve(n);
    vector<bool> used(n);
    dfs(s, used, cur, ans);
    return ans;
  }

private:
  void dfs(const string &s, vector<bool> &used, string &cur, vector<string> &ans) {
    int n = s.size();
    if ((int)cur.size() == n) { ans.push_back(cur); return; }
    for (int i = 0; i < n; ++i) {
      if (used[i]) continue;
      if (i > 0 && s[i] == s[i-1] && !used[i-1]) continue;
      used[i] = true;
      cur.push_back(s[i]);
      dfs(s, used, cur, ans);
      cur.pop_back();
      used[i] = false;
    }
  }
};

Java

import java.util.*;

class Solution2 {
  public List<String> permute(String s) {
    List<String> ans = new ArrayList<>();
    if (s == null || s.length() == 0) return ans;
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    boolean[] used = new boolean[arr.length];
    StringBuilder cur = new StringBuilder();
    dfs(arr, used, cur, ans);
    return ans;
  }

  private void dfs(char[] arr, boolean[] used, StringBuilder cur, List<String> ans) {
    if (cur.length() == arr.length) {
      ans.add(cur.toString());
      return;
    }
    for (int i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      if (i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue;
      used[i] = true;
      cur.append(arr[i]);
      dfs(arr, used, cur, ans);
      cur.deleteCharAt(cur.length() - 1);
      used[i] = false;
    }
  }
}

Python

class Solution2:
  def permute(self, s: str) -> list[str]:
    n = len(s)
    if n == 0: return []
    arr = sorted(s)
    used = [False] * n
    ans: list[str] = []

    def dfs(cur: list[str]) -> None:
      if len(cur) == n:
        ans.append(''.join(cur))
        return
      for i in range(n):
        if used[i]:
          continue
        if i > 0 and arr[i] == arr[i-1] and not used[i-1]:
          continue
        used[i] = True
        cur.append(arr[i])
        dfs(cur)
        cur.pop()
        used[i] = False

    dfs([])
    return ans

Complexity

• ⏰ Time complexity: O(n * P) where P is number of permutations produced; backtracking visits each permutation once and spends O(n) work to build it.
• 🧺 Space complexity: O(n + P*n) including output; O(n) auxiliary.