Leetcode discuss: 839. Similar String Groups

 Here is the link. 

Lesson learned - C# - Union Find - FindParent API - Union API - Failed

Jan. 6, 2020
Introduction
It is the last algorithm of my Leetcode mock facebook onsite interview. I wrote Union Find algorithm and came cross failed test case.

Failed test case - 60/77
"kccomwcgcs","socgcmcwkc","sgckwcmcoc","coswcmcgkc","cowkccmsgc","cosgmccwkc","sgmkwcccoc","coswmccgkc","kowcccmsgc","kgcomwcccs
The string is marked using index starting from 0.
0 - kccomwcgcs
1 - socgcmcwkc
2 - sgckwcmcoc
3 - coswcmcgkc
4 - cowkccmsgc
5 - cosgmccwkc
6 - sgmkwcccoc
7 - coswmccgkc
The string is denoted as strs, so strs[3] and strs[7] are similar, so Parents[7] = 3; later strs[5] and strs[7] are similar, so Parents[7] = 5; actually the first one is to union 3 and 5, second one is to union 5 and 7. But my code turned out missing first similar pair 3 and 7.

The parents array is wrong, the detail is the following:
parent[0] = 0,
parent[1] = 1
parent[2] = 2
parent[3] = 3
parent[4] = 4
parent[5] = 5
parent[6] = 2
parent[7] = 5
parent[8] = 4
parent[9] = 0

Actually parent[7] = 3, parent[7] = 5, so 3, and 5 and 7 should be one group. One of correct solution is the following:
parent[0] = 0,
parent[1] = 1
parent[2] = 2
parent[3] = 5
parent[4] = 4
parent[5] = 5
parent[6] = 2
parent[7] = 5
parent[8] = 4
parent[9] = 0

What is happening?
The statement in the following should be corrected:

parents[j] = FindParent(i, parents);

It should be:

parents[FindParent(j, parents)] = FindParent(i, parents);

The following code could not pass online judge. I wrote in my Leetcode premium Facebook mock interview.

Union API
The union API should be remembered. There are two FindParent calls in the statement.

public class Solution {
    // union find algorithm
    public int NumSimilarGroups(string[] strs) {
        if(strs == null || strs.Length <= 1)
            return 0; 
        
        var length = strs.Length;         
        var parents = new int[length];
        
        for(int i = 0; i < length; i++)
        {
            parents[i] = i; 
        }
        
        for(int i = 0; i < length - 1; i++)
        {
            var first = strs[i];
            
            for(int j = i + 1; j < length; j++)
            {
                var second = strs[j]; 
                
                if(runSimilarCheck(first, second))
                {                     
                    parents[j] = FindParent(i, parents); // Union i and j API - it should have two FindParent API calls in the statement - added after mock interview onsite
                }
            }
        }
        
        // run again 
        for(int i = 0; i < length; i++)
        {
            parents[i] = FindParent(i, parents);
        }
        
        var count = 0; 
        for(int i = 0 ; i < length; i++)
        {
            if(i == parents[i])
            {
                count++; 
            }
        }
        
        return count; 
    }
    
    private bool runSimilarCheck(string s1, string s2)
    {
        var length = s1.Length; 
        
        var first = -1; 
        var second = -1; 
        var count = 0; 
        
        for(int i = 0; i < length; i++)
        {
            if(s1[i] != s2[i])
            {
                count++; 
                if(first == -1)
                {
                    first = i; 
                }
                else if(second == -1)
                {
                    second = i; 
                }
            }
        }
        
        return count == 0 || (count == 2 && s1[first] == s2[second] && s1[second] == s2[first]); 
    }
    
    private int FindParent(int start, int[] parents)
    {
        if(start != parents[start])
        {
            parents[start] = FindParent(parents[start], parents);
        }
        
        return parents[start];
    }
}