🚀🚀🚀 Bohot Hard. (union find). यश

TC : O(N^2 L a(N)). {L str ki length);
SC: O(N * L);

Code dekhne se phele badi mushik se mene tuhmare liye, kuch likha hai dekh lena. { 2 photo hai, 1-1 karke dekhna }.

Is sawal mein hamein ek string array diya gaya hai, jisme har string dusri string ke anagram hai, matlab unke alphabets same hai, bas unke letters ki jagah jagah khichi hui hai. Hamen batana hai ki kitne groups hain, jahan har group mein har string dusre strings se ek particular similarity ke karan connect hai.

Do strings ek dusre se connect honge agar dono strings same hote hain ya fir koi ek character exchange karke dono same ho jate hain. Jaise ki "tars" aur "rats" same hain kyunki hum positions 0 aur 2 ko exchange karke dono strings ko same bana sakte hain. Isi tarah "rats" aur "arts" bhi same hain. Lekin "star" dusre strings "tars", "rats" aur "arts" se similar nahi hai.
Jab hum similarity ke basis par sabhi strings ko groups mein divide karenge to hume 2 groups milenge: {"tars", "rats", "arts"} aur {"star"}. Yah dhyan rakhna zaroori hai ki "tars" aur "arts" ek hi group mein hain, lekin wo similar nahi hai. Formally, har group mein wo words honge jo kisi ek dusre word ke similar hain.

Hamare paas ek list hai jisme sabhi strings anagram hain aur humein yah batana hai ki kitne groups hain.
Is problem ko solve karne ke liye hum union-find data structure ka use karenge. Ham sabhi strings ke pairs ke beech similarity check karenge aur agar wo similar hote hain to unke corresponding elements ko union-find data structure mein merge karenge. Iske baad, jitne bhi distinct parent elements hain, unko count karenge aur yah count groups ka count hoga.
Code mein ham numSimilarGroups method use karenge jisme hum ek array of strings strs lenge aur usme se groups ka count nikal kar return karenge.

class UnionFind {
    int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
}

class Solution {
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isSimilar(strs[i], strs[j])) {
                    uf.union(i, j);
                }
            }
        }
        Set<Integer> groups = new HashSet<>();
        for (int i = 0; i < n; i++) {
            groups.add(uf.find(i));
        }
        return groups.size();
    }

    private boolean isSimilar(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }
        int diffCount = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diffCount++;
                if (diffCount > 2) {
                    return false;
                }
            }
        }
        return diffCount == 2;
    }
}

#DSA #Leetcode #dailychallenge #dailyproblem #data