Smallest String With Swaps
Real-world version: Smallest Label After Allowed ExchangesThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def smallest_string_with_swaps(s: str, pairs: list[list[int]]) -> str:public String smallestStringWithSwaps(String s, List<List<Integer>> pairs)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's