## Wednesday, January 6, 2021

### Leetcode discuss: 839. Similar String Groups

##### 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];
}
}``````