Well-Ordered Permutations of a String

Problem

Given a string s, print all permutations of s whose letters appear in non-decreasing order when compared case-insensitively (i.e., for every adjacent pair a,b in the permutation, tolower(a) <= tolower(b)). We call such permutations well-ordered.

Examples

Input: s = "Sumit"
Output: []   # no well-ordered permutation because 'u' follows 'S' in alphabetic order

Input: s = "Now"
Output: ["Now"]  # 'N'<'o'<'w' (case-insensitive)

Input: s = "Interview"
Output: (several well-ordered permutations; see examples in Solution)

Solution

Two straightforward approaches are common:

• Method 1 — generate all permutations and filter by the well-ordered predicate (simple, easy to implement).
• Method 2 — constructive backtracking that enforces the non-decreasing condition while building the permutation (more efficient since it prunes invalid partial permutations early).

Method 1 — Generate & filter (backtracking)

Intuition

Generate every permutation of the characters in s, then check whether the permutation is well-ordered by comparing adjacent characters case-insensitively. This is straightforward but does unnecessary work when many permutations fail the predicate.

Approach

• Convert s to a char array arr.
• Use classic permutation generation by swapping (backtracking).
• When a complete permutation is produced, check that for all i, tolower(arr[i]) <= tolower(arr[i+1]). If true, append it to ans.

Edge cases: empty string returns [""] or [] depending on convention; here we return [] for empty input.

Code

C++

class Solution {
public:
  vector<string> wellOrderedPermutations(string s) {
    if (s.empty()) return {};
    vector<string> ans;
    function<void(int)> dfs = [&](int i) {
      if (i == (int)s.size()) {
        if (isWell(s)) ans.push_back(s);
        return;
      }
      for (int j = i; j < (int)s.size(); ++j) {
        swap(s[i], s[j]);
        dfs(i+1);
        swap(s[i], s[j]);
      }
    };
    dfs(0);
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    return ans;
  }

private:
  bool isWell(const string &t) {
    for (int i = 0; i + 1 < (int)t.size(); ++i) {
      if (tolower(t[i]) > tolower(t[i+1])) return false;
    }
    return true;
  }
};

Go

package main

import "unicode"

func wellOrderedPermutations(s string) []string {
  if len(s) == 0 { return []string{} }
  runes := []rune(s)
  ans := map[string]struct{}{}
  var dfs func(int)
  dfs = func(i int) {
    if i == len(runes) {
      str := string(runes)
      if isWell(str) { ans[str] = struct{}{} }
      return
    }
    for j := i; j < len(runes); j++ {
      runes[i], runes[j] = runes[j], runes[i]
      dfs(i+1)
      runes[i], runes[j] = runes[j], runes[i]
    }
  }
  dfs(0)
  res := make([]string, 0, len(ans))
  for k := range ans { res = append(res, k) }
  return res
}

func isWell(s string) bool {
  rs := []rune(s)
  for i := 0; i+1 < len(rs); i++ {
    if unicode.ToLower(rs[i]) > unicode.ToLower(rs[i+1]) { return false }
  }
  return true
}

Java

import java.util.*;

class Solution {
  public List<String> wellOrderedPermutations(String s) {
    if (s == null || s.isEmpty()) return Collections.emptyList();
    List<String> ans = new ArrayList<>();
    char[] arr = s.toCharArray();
    dfs(arr, 0, ans);
    Collections.sort(ans);
    return new ArrayList<>(new LinkedHashSet<>(ans));
  }

  private void dfs(char[] arr, int i, List<String> ans) {
    if (i == arr.length) {
      if (isWell(arr)) ans.add(new String(arr));
      return;
    }
    for (int j = i; j < arr.length; j++) {
      swap(arr, i, j);
      dfs(arr, i+1, ans);
      swap(arr, i, j);
    }
  }

  private boolean isWell(char[] a) {
    for (int i = 0; i + 1 < a.length; i++) {
      if (Character.toLowerCase(a[i]) > Character.toLowerCase(a[i+1])) return false;
    }
    return true;
  }

  private void swap(char[] a, int i, int j) {
    char t = a[i]; a[i] = a[j]; a[j] = t;
  }
}

Kotlin

class Solution {
  fun wellOrderedPermutations(s: String): List<String> {
    if (s.isEmpty()) return emptyList()
    val ans = mutableSetOf<String>()
    val arr = s.toCharArray()
    fun dfs(i: Int) {
      if (i == arr.size) {
        if (isWell(arr)) ans.add(String(arr))
        return
      }
      for (j in i until arr.size) {
        val tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp
        dfs(i+1)
        val tmp2 = arr[i]; arr[i] = arr[j]; arr[j] = tmp2
      }
    }
    dfs(0)
    return ans.toList().sorted()
  }

  private fun isWell(a: CharArray): Boolean {
    for (i in 0 until a.size - 1) if (a[i].lowercaseChar() > a[i+1].lowercaseChar()) return false
    return true
  }
}

Python

class Solution:
    def well_ordered_permutations(self, s: str) -> list[str]:
        if not s:
            return []
        arr = list(s)
        n = len(arr)
        ans: set[str] = set()

        def dfs(i: int) -> None:
            if i == n:
                t = ''.join(arr)
                if all(arr[k].lower() <= arr[k+1].lower() for k in range(n-1)):
                    ans.add(t)
                return
            for j in range(i, n):
                arr[i], arr[j] = arr[j], arr[i]
                dfs(i+1)
                arr[i], arr[j] = arr[j], arr[i]

        dfs(0)
        return sorted(ans)

Rust

pub struct Solution;
impl Solution {
    pub fn well_ordered_permutations(s: String) -> Vec<String> {
        if s.is_empty() { return Vec::new(); }
        let mut chars: Vec<char> = s.chars().collect();
        let mut ans = std::collections::BTreeSet::new();
        fn is_well(v: &Vec<char>) -> bool { for i in 0..v.len()-1 { if v[i].to_lowercase().next().unwrap() > v[i+1].to_lowercase().next().unwrap() { return false } } true }
        fn dfs(chars: &mut Vec<char>, i: usize, ans: &mut std::collections::BTreeSet<String>) {
            if i == chars.len() { if is_well(chars) { ans.insert(chars.iter().collect()); } return }
            for j in i..chars.len() {
                chars.swap(i,j);
                dfs(chars, i+1, ans);
                chars.swap(i,j);
            }
        }
        dfs(&mut chars, 0, &mut ans);
        ans.into_iter().collect()
    }
}

Complexity

• ⏰ Time complexity: O(n! * n) for Method 1 — generating n! permutations and checking each takes O(n). This is practical only for small n (n ≤ 8..10).
• 🧺 Space complexity: O(k * n) to store valid permutations where k is the number of well-ordered permutations; recursion stack O(n).

---

Method 2 — Constructive backtracking (enforce order while building)

Intuition

When building permutations, maintain the case-insensitive last character chosen and only place a character next if its lowercase is >= the previous lowercase. This prunes many branches early since any violation disqualifies the partial permutation.

Approach

• Convert s to a list of characters chars.
• Use a boolean used array to mark characters already placed.
• Build curr by trying each unused character c and only choose it if curr is empty or tolower(c) >= tolower(curr[-1]).
• Recurse until curr length becomes n; add curr to ans.
• Use a set to avoid duplicates when input contains repeated letters.

Code (Python)

class Solution:
    def well_ordered_permutations_constructive(self, s: str) -> list[str]:
        if not s: return []
        chars = list(s)
        n = len(chars)
        used = [False]*n
        ans = set()
        curr = []

        def dfs():
            if len(curr) == n:
                ans.add(''.join(curr))
                return
            prev = curr[-1].lower() if curr else None
            seen = set()
            for i in range(n):
                if used[i] or chars[i] in seen: continue
                if prev is not None and chars[i].lower() < prev: continue
                seen.add(chars[i])
                used[i] = True
                curr.append(chars[i])
                dfs()
                curr.pop()
                used[i] = False

        dfs()
        return sorted(ans)

Complexity

• ⏰ Time complexity: depends on pruning; worst-case still O(n! * n) but often much smaller in practice.
• 🧺 Space complexity: O(k * n) for output plus O(n) recursion stack.

Notes

• Method 2 is more efficient when many permutations violate the ordering early; Method 1 is simpler to implement and fine for very small strings.
• Treat characters case-sensitively in output but comparisons are case-insensitive.

References

• Original post: Find All the Well-Ordered Permutations of a Given String