839. Similar String Groups Hard

1/**
2 * [839] Similar String Groups
3 *
4 * Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.
5 * For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".
6 * Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}.  Notice that "tars" and "arts" are in the same group even though they are not similar.  Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.
7 * We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?
8 *  
9 * Example 1:
10 * 
11 * Input: strs = ["tars","rats","arts","star"]
12 * Output: 2
13 * 
14 * Example 2:
15 * 
16 * Input: strs = ["omv","ovm"]
17 * Output: 1
18 * 
19 *  
20 * Constraints:
21 * 
22 * 	1 <= strs.length <= 300
23 * 	1 <= strs[i].length <= 300
24 * 	strs[i] consists of lowercase letters only.
25 * 	All words in strs have the same length and are anagrams of each other.
26 * 
27 */
28pub struct Solution {}
29
30// problem: https://leetcode.com/problems/similar-string-groups/
31// discuss: https://leetcode.com/problems/similar-string-groups/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35impl Solution {
36    pub fn num_similar_groups(strs: Vec<String>) -> i32 {
37        0
38    }
39}
40
41// submission codes end
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn test_839() {
49    }
50}
51