> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/06-25-2022-1102.-smallest-string-with-swaps.md).

# 06/25/2022 1102. Smallest String With Swaps

Method: This question actually is a graph problem. We can use disjoint set to solve this question. First we iterate the pairs, and perform union operation for each vertex. Then we create a hashmap to store integer and list of integer. Iterate the string s, for each char index we perform the find operation to find the root. Store the char index in the list corresponding to root in this hashmap. Then we iterate the lists in the hashmap, for each list indices, we find the corresponding char in the s and put it into a character list and sort this character list.  **Then we iterate over the indices list and character, place the ith characters at the ith index in the string smallString.** 

Time O(V + VlogV + E \* alpha V)

Space O(V + logV)