55. Print All Permutations of a String

Given a string s of distinct characters, print all of its permutations, sorted in ascending alphabetical order and space-separated on one line.

Input: The input is a single line containing the string s, whose characters are all distinct. Output: Print all permutations of s, sorted alphabetically and space-separated on one line.

1 <= |s| <= 8, all characters of s are distinct

This problem's constraint explicitly states all characters of s are DISTINCT - if repeated characters were allowed, some fix-choices would generate identical permutations, requiring an extra deduplication step (unlike here).

Print every possible reordering (permutation) of a string's characters, sorted alphabetically. Brute force: This problem's very nature IS the brute-force enumeration - there are exactly n! permutations of n distinct characters, and the problem genuinely requires generating all of them, so there's no way to avoid visiting each one. Optimised: The recursive 'fix one character, permute the rest' approach generates each of the n! permutations exactly once, with no wasted or duplicate work, since distinct characters guarantee no two different fix-choices ever produce the same permutation - efficient generation, even though the total OUTPUT size is inherently factorial.

First sort the input string's characters ascending, then generate permutations via backtracking while always trying the remaining unused characters in ascending order at each recursive position. Because candidates are always tried from smallest to largest at every level of the recursion, the permutations are produced already in lexicographic order, with no separate sort of the output needed afterward. This removes the O(n! log(n!)) sorting overhead of the brute approach while doing the same amount of generation work. Time: O(n! * n) Space: O(n! * n)

Generate all permutations of the string using standard backtracking (at each step, pick any not-yet-used character and recurse), collect them all into a list, then sort that list of strings lexicographically and print them. This is correct since sorting after the fact always yields ascending order regardless of the order permutations were generated in, but it pays an extra sorting cost on top of already having to generate all n! permutations. Time: O(n! * n log(n!)) Space: O(n! * n)

Sort the string once, print it, and then repeatedly transform it into the lexicographically next permutation in place using the standard algorithm: scan from the right to find the rightmost position where the sequence increases, swap it with the smallest character to its right that is still larger than it, and reverse the suffix after that position, until no next permutation exists. Since there are inherently n! permutations of length n to output, the time cannot drop below that, but this approach needs no recursion stack and no extra per-call arrays, generating each next string in place using only a handful of index variables. Time: O(n! * n) Space: O(1) extra (excluding output)

1. Recursively fix each character in turn as the FIRST character of the current arrangement. 2. For each choice, recursively permute the REMAINING characters to fill the rest of the positions. 3. Once a full-length arrangement is built, record it; after all recursive branches finish, sort every recorded permutation before printing.

Time: O(n! * n) - there are n! permutations, and each takes O(n) to construct/output, and the small constraint (|s| <= 8) keeps 8! = 40320 permutations entirely manageable. Space: O(n! * n), for storing all generated permutations before the final sort and print.

s of length 1 (a single permutation, s itself); s of length 8, producing 8! = 40320 permutations, testing generation and sort performance.

Be ready to also produce permutations in a SPECIFIC generation order (like lexicographic, without needing a final sort) using Heap's algorithm or the 'next permutation' technique, as a common, more advanced follow-up.