0576MediumArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-FindSorting

Smallest Label After Allowed Exchanges

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A label is printed as the lowercase string s, one letter per slot, numbered from 0.

The printer can exchange the letters in certain slots. Each entry pairs[i] = [a, b] says the letters in slots a and b may trade places. An exchange listed in pairs may be carried out as often as you like, in any order, and the same entry may appear more than once. An entry may also name the same slot twice, which changes nothing.

Return the alphabetically earliest label reachable through any number of these exchanges.

Examples

Example 1

Input: s = "mzbqta", pairs = [[0, 5], [2, 4]]
Output: "azbqtm"

Slots 0 and 5 hold m and a and may trade, so a moves to the front. Slots 2 and 4 hold b and t and may trade, but b is already the earlier letter. Slots 1 and 3 appear in no entry.

Example 2

Input: s = "zyxwvu", pairs = [[0, 3], [3, 5], [1, 4]]
Output: "uvxwyz"

Slots 0, 3 and 5 are linked into one group holding z, w and u, so those three letters end up as u, w, z across slots 0, 3 and 5. Slots 1 and 4 form a second group holding y and v, which come out as v then y. Slot 2 keeps x.

Example 3

Input: s = "fedcba", pairs = [[0, 1], [2, 3], [4, 5]]
Output: "efcdab"

There are three separate groups of two slots each, and no letter can leave its own group, so each pair simply comes out in alphabetical order.

Constraints

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s holds lowercase English letters only.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def smallest_string_with_swaps(s: str, pairs: list[list[int]]) -> str:

Java

public String smallestStringWithSwaps(String s, List<List<Integer>> pairs)

The intended approach

Time O(n log n + p) — the merges are near constant each and the letters of every group are sorted once.Space O(n) for the forest, the buckets and the label handed back.

Treat the slots as nodes and each listed exchange as an undirected link. Slots inside one linked group can be shuffled into any arrangement, so the letters currently in a group can be redistributed over that group's slots however you like, while letters never cross between groups. A disjoint-set forest with path halving merges the pairs in near-linear time. Then bucket the slots by their representative, sort each bucket's letters, and write them back into that bucket's slots in increasing slot order, which puts the smallest letter as early on the label as it can go.

Pythonentry point: smallest_string_with_swaps

def smallest_string_with_swaps(s, pairs):
    # O(n log n + p) time, O(n) space: positions joined by a chain of allowed
    # exchanges can be rearranged freely among themselves, so a disjoint-set
    # forest merges every listed pair, then each group's own letters are sorted
    # and written back into that group's positions in increasing order.
    n = len(s)
    root = list(range(n))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for a, b in pairs:
        ra = find(a)
        rb = find(b)
        if ra != rb:
            root[rb] = ra
    groups = {}
    for i in range(n):
        groups.setdefault(find(i), []).append(i)
    out = [""] * n
    for members in groups.values():
        letters = sorted(s[i] for i in members)
        for i in range(len(members)):
            out[members[i]] = letters[i]
    return "".join(out)

The obvious version

Search the labels themselves. Starting from the printed label, repeatedly apply every listed exchange to every label already discovered, collecting each new label in a queue, and report the alphabetically earliest label the search ever reaches.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_smallest_string_with_swaps(s, pairs):
    from collections import deque
    start = s
    seen = {start}
    queue = deque([start])
    best = start
    while queue:
        cur = queue.popleft()
        if cur < best:
            best = cur
        for a, b in pairs:
            if a == b:
                continue
            letters = list(cur)
            letters[a], letters[b] = letters[b], letters[a]
            nxt = "".join(letters)
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in