Rearrange Through Links

Medium

You are given a string text of lowercase English letters and a list links, where each link [a, b] is a pair of positions in the string (0-based). The letters at the two positions of any link may be swapped, as many times as you like and in any order. Return the lexicographically smallest string you can turn text into using these swaps.

Example 1

text="lkji", links=[[0, 2], [1, 3]] → 'jilk'

Swap positions 0 and 2 ("jkli"), then positions 1 and 3, which gives "jilk".

Example 2

text="post", links=[[0, 1], [1, 3]] → 'opst'

Positions 0, 1 and 3 are chained together, so their letters p, o, t can be arranged freely as o, p, t. The s at position 2 stays put.

Example 3

text="ba", links=[] → 'ba'

There are no links, so nothing can move.

Constraints

1 ≤ len(text) ≤ 10⁵
0 ≤ len(links) ≤ 10⁵
0 ≤ links[i][0], links[i][1] < len(text)
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Array Hash Table String Sorting

Similar problems

Merge Contact Cards Medium Chains of Synonyms Medium One-Swap Word Families Hard Ratio Chain Queries Medium A Board Cut by Slashes Medium

Input

text="lkji", links=[[0, 2], [1, 3]]

Expected

'jilk'

Run checks the first 3 tests in your browser. Submit checks all 77 tests on the server, hidden ones included.