You get a string s of lowercase letters and a list pairs. Each pair [a, b] names two positions of s (counting from 0) whose letters you may swap. You can use any pair as often as you like, in any order, or not at all.
Write smallest_string_with_swaps(s: str, pairs: list[list[int]]) -> str: the alphabetically smallest string you can reach, compared letter by letter the way Python's < compares strings.
Examples:
smallest_string_with_swaps("trace", [[0, 1], [1, 2], [3, 4]]) # "artce"
Positions 0, 1 and 2 are linked through position 1, so their letters t, r, a can be put in any order among them, even though no pair joins 0 and 2 directly. Sorted, they read a, r, t. Positions 3 and 4 swap c and e, which are already in order.
smallest_string_with_swaps("zebra", [[0, 4], [1, 3]]) # "aebrz" swap 0 and 4; e and r stay
smallest_string_with_swaps("melon", []) # "melon" nothing can move
Constraints:
1 <= len(s) <= 10^5and0 <= len(pairs) <= 10^5.0 <= a, b < len(s). A pair may havea == b(it does nothing), and the same pair can appear more than once.
⭐ Bonus: a speed test with 60,000-letter strings (one of them linked by a single long chain of pairs) earns a star in about O((n + p) log n), where n = len(s) and p = len(pairs).
Show hint
if position x can trade with y and y with z, a few swaps move any arrangement of those three letters into any other. So the pairs split the positions into groups, and inside a group you can put the letters in any order you like.