List All Permutations of an Alphanumeric String in Digit, Lowercase, Uppercase Order

Given a string s made of digits, lowercase letters and uppercase letters, return all permutations of s, sorted in a custom character order: digits come first, then lowercase letters, then uppercase letters.

Function Signature

def ordered_permutations(s: str) -> list[str]:

Rules

• A permutation is a string that uses every character of s exactly as many times as it appears in s, in some order.
• Characters are ranked as follows: every digit ranks below every lowercase letter, and every lowercase letter ranks below every uppercase letter. Within a group the usual order applies: 0 to 9, a to z, A to Z.
• Permutations are ordered by the first position at which they differ, using this rank. All permutations have the same length, so this order is total.
• If s contains repeated characters, each distinct permutation appears exactly once.
• This order is not the default string order: in ASCII, uppercase letters sort before lowercase letters.

Constraints

• 1 <= len(s) <= 8
• Every character of s is in 0-9, a-z or A-Z.
• The output has at most 8! = 40,320 strings.

Examples

Example 1

Input:  s = "aB1"
Output: ["1aB", "1Ba", "a1B", "aB1", "B1a", "Ba1"]

The characters rank 1, then a, then B.

Example 2

Input:  s = "Ab"
Output: ["bA", "Ab"]

The lowercase b ranks below the uppercase A, so "bA" comes first, although default string comparison would put "Ab" first.

Example 3

Input:  s = "z0z"
Output: ["0zz", "z0z", "zz0"]

The two z characters are identical, so there are only three distinct permutations.

Distinct Permutations in Digit, Lowercase, Uppercase Order

Given a string s made of digits, lowercase letters and uppercase letters, return all distinct permutations of s, sorted in a custom character order: digits come first, then lowercase letters, then uppercase letters.

Implement ordered_permutations(s), which returns the permutations as a list of strings.

Rules:

• A permutation is a string that uses every character of s exactly as many times as it appears in s, in some order.
• Characters are ranked as follows: every digit ranks below every lowercase letter, and every lowercase letter ranks below every uppercase letter. Within a group the usual order applies: 0 to 9, a to z, A to Z. A lowercase letter and its uppercase form (for example a and A) are different characters.
• Permutations are ordered by the first position at which they differ, using this rank, and the list goes from the lowest permutation to the highest. All permutations have the same length, so this order is total.
• If s contains repeated characters, each distinct permutation appears exactly once.
• This order is not the default string order: in ASCII, uppercase letters sort before lowercase letters. For example, for s = "Ab" the answer is ["bA", "Ab"], because the lowercase b ranks below the uppercase A.

No numeric value here comes close to 2^31 - 1.

Constraints:

• 1 <= len(s) <= 8
• Every character of s is in 0-9, a-z or A-Z; characters may repeat.
• The output has at most 8! = 40,320 strings.

Example 1:

Input: s = "aB1"
Output: ["1aB", "1Ba", "a1B", "aB1", "B1a", "Ba1"]

The characters rank 1, then a, then B.

Example 2:

Input: s = "z0z"
Output: ["0zz", "z0z", "zz0"]

The two z characters are identical, so there are only three distinct permutations.

Hints

1. Give every character a numeric rank (digits lowest, then lowercase, then uppercase) so that comparing characters in the custom order becomes comparing numbers.
2. Default string comparison puts uppercase before lowercase, so do not rely on it for the final order.
3. When s repeats a character, swapping two copies of it gives the same string; make sure each distinct permutation is produced only once.

Approach

Map every character to a numeric rank: digits 0-9 get 0-9, lowercase a-z get 10-35, uppercase A-Z get 36-61 (the index of the character in the string "0123456789abc...zABC...Z"). Comparing two permutations under the problem's order is then plain lexicographic comparison of their rank sequences. Sorting the ranks ascending gives the lowest permutation. The algorithm repeatedly emits the current sequence (mapped back to characters) and advances it to its immediate lexicographic successor with the standard next-permutation step: find the rightmost index i with r[i] < r[i+1]; if there is none the sequence is non-increasing, which is the highest permutation, so stop; otherwise swap r[i] with the rightmost r[j] > r[i] and reverse the suffix after i. Invariant: each emitted sequence is the smallest arrangement strictly greater than the previous one, so every distinct arrangement is produced exactly once, in ascending order, from the lowest to the highest. Because both scans use strict comparisons, two equal characters are never treated as an increase, so repeated characters never produce a duplicate permutation. Edge cases: a single character, or all characters identical, gives exactly one string; letters that differ only in case (a and A) must follow the custom rank (a below A), not ASCII order, where uppercase comes first.

• Time complexity: O(n * P), where P <= n! (at most 40,320) is the number of distinct permutations
• Space complexity: O(n * P) for the output, O(n) extra