1202. Smallest String With Swaps Medium

1/**
2 * [1202] Smallest String With Swaps
3 *
4 * You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.
5 * You can swap the characters at any pair of indices in the given pairs any number of times.
6 * Return the lexicographically smallest string that s can be changed to after using the swaps.
7 *  
8 * Example 1:
9 * 
10 * Input: s = "dcab", pairs = [[0,3],[1,2]]
11 * Output: "bacd"
12 * Explaination: 
13 * Swap s[0] and s[3], s = "bcad"
14 * Swap s[1] and s[2], s = "bacd"
15 * 
16 * Example 2:
17 * 
18 * Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
19 * Output: "abcd"
20 * Explaination: 
21 * Swap s[0] and s[3], s = "bcad"
22 * Swap s[0] and s[2], s = "acbd"
23 * Swap s[1] and s[2], s = "abcd"
24 * Example 3:
25 * 
26 * Input: s = "cba", pairs = [[0,1],[1,2]]
27 * Output: "abc"
28 * Explaination: 
29 * Swap s[0] and s[1], s = "bca"
30 * Swap s[1] and s[2], s = "bac"
31 * Swap s[0] and s[1], s = "abc"
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	1 <= s.length <= 10^5
37 * 	0 <= pairs.length <= 10^5
38 * 	0 <= pairs[i][0], pairs[i][1] < s.length
39 * 	s only contains lower case English letters.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/smallest-string-with-swaps/
45// discuss: https://leetcode.com/problems/smallest-string-with-swaps/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn smallest_string_with_swaps(s: String, pairs: Vec<Vec<i32>>) -> String {
51        String::new()
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_1202() {
63    }
64}
65