1027. The Smallest Arrangement Under Allowed Swaps

A word s of lowercase letters is given, together with m pairs of positions. Each pair names two positions whose letters may be exchanged, and a pair may be used as often as you like, in any order.

Print the smallest word, in dictionary order, that can be reached.

dcab, pairs (1 4) (3 2) -> bacd dcab, pairs (1 4) (3 2) (1 3) -> abcd cba, no pairs -> cba fedcba, pairs (1 2)(2 3)(3 4)(4 5)(5 6) -> abcdef

Positions are numbered from 1. In the first example the two pairs are separate, so position 1 can trade only with position 4 and position 2 only with position 3. Adding the pair (1 3) in the second example ties all four positions together, and then the whole word can be rearranged freely.

## What most people try first

Search the reachable words: start from s, apply every allowed swap, keep whatever is new, and repeat. It is correct and the number of reachable words is factorial in the size of a group, so it stops being usable at about eight letters.

The second attempt is to sort each pair, repeatedly, until nothing changes. That also works and there is no bound worth relying on for how many passes it takes.

## The pairs are not a list of swaps, they are a grouping

If positions i and j may trade and j and k may trade, then the letters at i, j and k can be put in ANY order among those three positions. Three swaps achieve any permutation of three items, and the same argument extends to a whole group: once the positions are connected, the letters in them can be arranged however you like.

So:

union the two positions of every pair bucket the positions by root for each bucket: take the letters at those positions and sort them write them back into the positions in increasing order of position

## Why this is the smallest reachable word

Within a group, the multiset of letters never changes, because a swap only moves letters between positions of one group. So the best any arrangement can do is to put the smallest letter of the group at the group's smallest position, the next smallest at the next position, and so on, and that is reachable because any permutation inside a group is reachable. Letters in different groups never meet, so the choices are independent and doing the best in each group gives the best overall.

## The detail that decides correctness

The sorted letters go back in increasing order of POSITION, not in the order the positions happened to be collected. Collecting them by walking the word from left to right gives increasing positions for free; collecting them from a map of roots does not, and the letters land scrambled within the group.

## The pairs that change nothing

A pair naming one position twice, and a pair repeated, both merge nothing. Neither needs a special case.

## Cross-reference

Problem 1031 uses the same grouping of positions and asks for the fewest mismatches against a target rather than the smallest arrangement, so it compares two multisets per group instead of sorting one.

## Cost

Time O((n + m) alpha(n) + n log n). Space O(n).

Sorting each bucket separately totals O(n log n) across the word, because the bucket sizes add up to n. Counting the 26 letters of each bucket instead removes the logarithm, which is worth knowing and is not needed at these limits.

Constraints - `1 ≤ length of s ≤ 100000` - `0 ≤ m ≤ 100000` - `1 ≤ i, j ≤ length of s` - Every character of `s` is a lowercase English letter. - `i` may equal `j`, and a pair may repeat.