You hold a string s and a list pairs of index pairs [i, j]. You may swap the characters at positions i and j of any listed pair, any number of times and in any order. Return the lexicographically smallest string obtainable.
Examples
Input: s = "dcab", pairs = [[0, 3], [1, 2]]
Output: "bacd"
Explanation: positions {0, 3} hold d and b; positions {1, 2} hold c and a. Each group is sorted independently.
Input: s = "dcab", pairs = [[0, 3], [1, 2], [0, 2]]
Output: "abcd"
Explanation: all four positions are connected, so any arrangement is reachable.
Input: s = "cba", pairs = []
Output: "cba"
Constraints
0 <= len(s) <= 10**4,0 <= len(pairs) <= 2 * 10**4, lowercase letters only- Target: O((n + P) * alpha(n) + n log n) time.
Goals
- Realise that swappable positions form groups that can be permuted freely
- Sort the characters of each group and write them back in position order