755. Swap-Allowed Smallest
A sign painter has a row of letter tiles forming the lowercase string s (positions are numbered from 0). Each entry [i, j] of pairs means the tiles at positions i and j may be exchanged. Any exchange from the list may be used any number of times and in any order, and a tile may travel through several exchanges.
Return the lexicographically smallest string that can be produced. If pairs is empty, or no exchange helps, the original string is the answer. Strings are compared character by character from the left using alphabetical order.
Example 1
- Input:
- s = "dcab", pairs = [[0,3],[1,2]]
- Output:
- "bacd"
- Explanation:
Positions 0 and 3 hold d and b, positions 1 and 2 hold c and a. Sorting the letters inside each group of positions gives
bacd.
Example 2
- Input:
- s = "cba", pairs = [[0,1],[1,2]]
- Output:
- "abc"
- Explanation:
The swaps chain all three positions together, so the letters can be fully sorted into
abc.
Example 3
- Input:
- s = "dcba", pairs = [[0,1]]
- Output:
- "cdba"
- Explanation:
Only the first two letters can be exchanged: d and c become c and d, giving
cdba.
Constraints
- 1 ≤ s.length ≤ 105
- 0 ≤ pairs.length ≤ 105
- 0 ≤ i, j < s.length and i ≠ j
- s consists of lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n log n + m alpha(n))
- Space
- O(n)