Code Implementation

class Solution:
    def numSimilarGroups(self, strs):
        def are_similar(a, b):
            diff = 0
            for x, y in zip(a, b):
                if x != y:
                    diff += 1
                    if diff > 2:
                        return False
            return diff == 2 or diff == 0

        n = len(strs)
        parent = [i for i in range(n)]

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py

        for i in range(n):
            for j in range(i + 1, n):
                if are_similar(strs[i], strs[j]):
                    union(i, j)

        groups = set()
        for i in range(n):
            groups.add(find(i))
        return len(groups)
      

class Solution {
public:
    bool areSimilar(const string& a, const string& b) {
        int diff = 0;
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] != b[i]) {
                ++diff;
                if (diff > 2) return false;
            }
        }
        return diff == 2 || diff == 0;
    }
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        vector<int> parent(n);
        for (int i = 0; i < n; ++i) parent[i] = i;

        function<int(int)> find = [&](int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };

        auto unite = [&](int x, int y) {
            int px = find(x), py = find(y);
            if (px != py) parent[px] = py;
        };

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (areSimilar(strs[i], strs[j])) unite(i, j);
            }
        }

        unordered_set<int> groups;
        for (int i = 0; i < n; ++i) groups.insert(find(i));
        return groups.size();
    }
};
      

class Solution {
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        int[] parent = new int[n];
        for (int i = 0; i < n; ++i) parent[i] = i;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (areSimilar(strs[i], strs[j])) {
                    union(parent, i, j);
                }
            }
        }

        Set<Integer> groups = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            groups.add(find(parent, i));
        }
        return groups.size();
    }

    private boolean areSimilar(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); ++i) {
            if (a.charAt(i) != b.charAt(i)) {
                diff++;
                if (diff > 2) return false;
            }
        }
        return diff == 2 || diff == 0;
    }

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

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

var numSimilarGroups = function(strs) {
    const n = strs.length;
    const parent = Array(n).fill(0).map((_, i) => i);

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

    function union(x, y) {
        let px = find(x), py = find(y);
        if (px !== py) parent[px] = py;
    }

    function areSimilar(a, b) {
        let diff = 0;
        for (let i = 0; i < a.length; ++i) {
            if (a[i] !== b[i]) {
                diff++;
                if (diff > 2) return false;
            }
        }
        return diff === 2 || diff === 0;
    }

    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            if (areSimilar(strs[i], strs[j])) {
                union(i, j);
            }
        }
    }

    const groups = new Set();
    for (let i = 0; i < n; ++i) groups.add(find(i));
    return groups.size;
};
      

Problem Description

Given an array of strings strs, where each string contains the same number of characters and consists of lowercase English letters, we define two strings as "similar" if you can swap any two letters (in different positions) in one string to get the other string. A group is a set of strings where each string is similar (directly or transitively) to at least one other string in the group.

Your task is to return the number of groups of similar strings in strs. Each string belongs to exactly one group. Two strings are similar if they are equal, or if you can swap two characters in one string to make it equal to the other.

• Each string in strs can only be used once in a group.
• All strings in strs are of the same length.
• There is exactly one valid grouping for the input.

Thought Process

To solve this problem, we first need to understand what it means for two strings to be similar. If two strings differ in exactly two positions, and swapping those two letters in one string makes it equal to the other, they are similar. Furthermore, similarity is transitive: if A is similar to B and B to C, then A is in the same group as C.

The brute-force approach would be to compare every pair of strings to check if they are similar and then somehow group them. But this can be inefficient if the input is large. To optimize, we can model this as a graph problem: strings are nodes, and there is an edge between two nodes if the strings are similar. Then, the number of groups is the number of connected components in the graph.

This leads us to use a Disjoint Set Union (Union-Find) data structure, which helps efficiently group connected components.

Solution Approach

• Step 1: Model the Problem as a Graph
  Each string is a node. If two strings are similar, draw an edge between them.
• Step 2: Similarity Check
  For two strings of equal length, count the number of positions where their characters differ. If the count is exactly 2 (or 0, for identical strings), they are similar.
• Step 3: Union-Find Data Structure
  Use Union-Find to keep track of connected components. Initially, each string is its own parent. For every pair of similar strings, union their groups.
• Step 4: Count Groups
  After all unions, the number of unique parents (roots) in the Union-Find structure is the number of groups.
• Why Union-Find?
  Union-Find is efficient for merging sets and finding the representative of a set, making it ideal for counting connected components in a graph.

Example Walkthrough

Let's use the input ["tars", "rats", "arts", "star"].

• Compare each pair:
  • tars and rats: differ at positions 0 and 1. Similar.
  • tars and arts: differ at positions 0 and 2. Similar.
  • tars and star: differ at 0,1,2,3. Not similar.
  • rats and arts: differ at positions 0 and 1. Similar.
  • rats and star: differ at 0,1,2,3. Not similar.
  • arts and star: differ at 0,1,2,3. Not similar.
• After union operations for similar pairs, all of tars, rats, and arts end up in one group. star is alone.
• So, the answer is 2 groups.

Time and Space Complexity

• Brute-force: For each pair of strings (O(N^2)), check similarity (O(L) where L is the string length). So, O(N^2 * L).
• Optimized (Union-Find): We still check all pairs for similarity, so the time is O(N^2 * L). Union-Find operations are nearly constant time due to path compression.
• Space Complexity: O(N) for storing parents in Union-Find.

Summary

We modeled the problem as a graph where strings are nodes and similarity is an edge. Using Union-Find, we efficiently grouped similar strings and counted the number of groups. The key insight is recognizing transitive similarity and using a data structure that makes grouping efficient. This approach is both intuitive and performant for the constraints given.