Distinct Permutations

Given a string s of lowercase letters, return every distinct string that can be formed by rearranging all of its characters.

Each character of s must be used exactly once in every arrangement. If s contains repeated characters, arrangements that would be identical are counted only once, so the result contains no duplicates.

Return the distinct arrangements in alphabetical (lexicographic) order.

Examples

Example 1

Input: s = "aabac"
Output: ["aaabc","aaacb","aabac","aabca","aacab","aacba","abaac","abaca","abcaa","acaab","acaba","acbaa","baaac","baaca","bacaa","bcaaa","caaab","caaba","cabaa","cbaaa"]
Explanation: The characters a, a, a, b, c can be arranged into 5! / 3! = 20 distinct
strings, listed in alphabetical order.

Example 2

Input: s = "ab"
Output: ["ab","ba"]
Explanation: Two characters give two distinct arrangements.

Example 3

Input: s = "aaa"
Output: ["aaa"]
Explanation: Every arrangement of three identical characters is the same string, so
there is exactly one distinct result.