All Arrangements of a String
You are given a string s of lowercase English letters.
An arrangement of s uses every letter of s exactly once, in any order.
Return every distinct arrangement of s as a list of strings, sorted in dictionary order (alphabetical order).
Note
If s has repeated letters, some orderings give the same string. Include each string only once.
Build the string one position at a time. Keep a count of each letter that is still unused, and try the letters in alphabetical order. Each different letter gives a new branch, so no string is built twice, and the results come out already sorted.
Examples
Example 1
- Input:
- "cab"
- Output:
- ["abc","acb","bac","bca","cab","cba"]
All three letters are different, so there are 3 * 2 * 1 = 6 arrangements, listed in dictionary order.
Example 2
- Input:
- "aba"
- Output:
- ["aab","aba","baa"]
The two letters a are the same, so only 3 different strings can be made.
Example 3
- Input:
- "zz"
- Output:
- ["zz"]
Both letters are the same, so there is only one arrangement.
Constraints
1 <= s.length <= 7scontains only lowercase English letters.- In the hidden tests,
shas at most 60 distinct arrangements.
Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.