Adjacent Swaps to Match the Roster
Problem
Players stand in a line, each wearing a jersey letter; the current line reads current. The coach wants the line to read target, which uses exactly the same letters (possibly in a different order). The only allowed move swaps two neighbouring players.
Return the minimum number of moves needed. Players with the same letter are interchangeable.
Example 1
- Input:
- current = "abcd", target = "cdab"
- Output:
- 4
c and d must each pass both a and b: 2 + 2 = 4 neighbour swaps.
Example 2
- Input:
- current = "aab", target = "baa"
- Output:
- 2
The b moves two places to the front; the two a's need no relative change.
Constraints
- 1 ≤ current.length ≤ 10^5
- target is a rearrangement of current
- Both strings contain only lowercase English letters.
Hint
Show the first hint
If every letter were distinct, the answer would be a classic count: neighbour swaps needed to sort a permutation equals its number of inversions.
Walkthrough
How to approach it
01Clarify before coding
- Are players with the same letter interchangeable? Yes, only the letters must match.
- Is target always reachable? Yes, it is a rearrangement of current.
- How large can the answer be? About n²/2 ≈ 5·10^9 for n = 10^5: beyond 32 bits.
02Brute force
Greedy simulation: for each target position, find the nearest matching player to the right in the current line and bubble them left with neighbour swaps.
Cost: O(n²) swaps simulated: about 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.