Fewest Swaps to Rearrange

Hard

A shelf holds letter tiles that spell the string start. You want them to spell goal instead. In one move you may swap any two tiles. Both strings use exactly the same letters, just possibly in a different order. Return the smallest number of moves that turns start into goal.

Example 1

start="fade", goal="defa" → 2

Swapping letters 0 and 2 gives "dafe", then swapping letters 1 and 3 gives "defa": two swaps, and one is not enough.

Example 2

start="abba", goal="baab" → 2

Swap letters 0 and 1 to get "baba", then letters 2 and 3 to get "baab".

Example 3

start="cab", goal="cab" → 0

Constraints

1 ≤ len(start) ≤ 20
len(goal) == len(start)
both strings use only the letters a–f
goal is a rearrangement of start

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search String

Similar problems

One Letter at a Time Hard Letter Order From a Dictionary Hard Clear the Marble Row Hard Ball Into the Hole Hard Spelling a Word on a Dial Lock Hard

Input

start="fade", goal="defa"

Expected

Run checks the first 3 tests in your browser. Submit checks all 46 tests on the server, hidden ones included.