Smallest String With Swaps Problem

Smallest String With Swaps Problem — ExecCode Medium DSA Practice

Solve the Smallest String With Swaps problem on ExecCode. Free online medium DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You are given a string s and an array of pairs of indices in that string where each pair pairs[i] = [ai, bi] means you may swap the characters at positions ai and bi any number of times, in any order. Return the lexicographically smallest string that can be obtained by performing any sequence of the allowed swaps.

Examples

Input {"s": "dcab", "pairs": [[0, 3], [1, 2]]}; Output bacd. Input {"s": "dcab", "pairs": [[0, 3], [1, 2], [0, 2]]}; Output abcd. Input {"s": "cba", "pairs": [[0, 1], [1, 2]]}; Output abc

Constraints

1 ≤ s.length ≤ 10⁵ 0 ≤ pairs.length ≤ s.length 0 ≤ ai, bi < s.length s consists only of lowercase English letters.

Practice Smallest String With Swaps free on ExecCode. Browse DSA problems, topic map, and placement guides.