FunctionRacerProblemsRace

Distinct Arrangements in Order

MediumRecursionPython, JavaScript, TypeScript, Java, C++

word is a string of lowercase letters that may contain repeated letters. Return every distinct string that can be made by rearranging all of its letters, each exactly once, listed in alphabetical order. Rearrangements that only swap equal letters produce the same string, and that string must appear only once. The empty string has one arrangement, itself, so "" gives [""].

The recursive approach: sort the letters, choose each distinct letter in turn as the first character, and attach every arrangement of the remaining letters.

For example, "aab" gives ["aab", "aba", "baa"].

Example 1

word "aab"
returns ["aab","aba","baa"]

Starting with a leaves ab, giving aab and aba; starting with b leaves aa, giving baa. The second a would only repeat the first two.

Example 2

word "ab"
returns ["ab","ba"]

Two different letters give two arrangements, ab before ba.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems