839. Similar String Groups LeetCode Solution

Last updated: February 20, 2025

In this guide, you will get 839. Similar String Groups LeetCode Solution with the best time and space complexity. The solution to Similar String Groups problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Similar String Groups solution in C++
Similar String Groups solution in Java
Similar String Groups solution in Python
Additional Resources

839. Similar String Groups LeetCode Solution image

Problem Statement of Similar String Groups

Two strings, X and Y, are considered similar if either they are identical or we can make them equivalent by swapping at most two letters (in distinct positions) within the string X.
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”.
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.
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?

Example 1:

Input: strs = [“tars”,”rats”,”arts”,”star”]
Output: 2

Example 2:

Input: strs = [“omv”,”ovm”]
Output: 1

Constraints:

1 <= strs.length <= 300
1 <= strs[i].length <= 300
strs[i] consists of lowercase letters only.
All words in strs have the same length and are anagrams of each other.

Complexity Analysis

Time Complexity: O(nk \cdot \min(n, k)), where n = |\texttt{strs}| and k = |\texttt{strs[0]}|
Space Complexity: O(n)

839. Similar String Groups LeetCode Solution in C++

class Solution {
 public:
  int numSimilarGroups(vector<string>& strs) {
    int ans = 0;
    vector<bool> seen(strs.size());

    for (int i = 0; i < strs.size(); ++i)
      if (!seen[i]) {
        dfs(strs, i, seen);
        ++ans;
      }

    return ans;
  }

 private:
  void dfs(const vector<string>& strs, int i, vector<bool>& seen) {
    seen[i] = true;
    for (int j = 0; j < strs.size(); ++j)
      if (!seen[j] && isSimilar(strs[i], strs[j]))
        dfs(strs, j, seen);
  }

  bool isSimilar(const string& X, const string& Y) {
    int diff = 0;
    for (int i = 0; i < X.length(); ++i)
      if (X[i] != Y[i] && ++diff > 2)
        return false;
    return true;
  }
};
/* code provided by PROGIEZ */

839. Similar String Groups LeetCode Solution in Java

class Solution {
  public int numSimilarGroups(String[] strs) {
    int ans = 0;
    boolean[] seen = new boolean[strs.length];

    for (int i = 0; i < strs.length; ++i)
      if (!seen[i]) {
        dfs(strs, i, seen);
        ++ans;
      }

    return ans;
  }

  private void dfs(final String[] strs, int i, boolean[] seen) {
    seen[i] = true;
    for (int j = 0; j < strs.length; ++j)
      if (!seen[j] && isSimilar(strs[i], strs[j]))
        dfs(strs, j, seen);
  }

  private boolean isSimilar(final String X, final String Y) {
    int diff = 0;
    for (int i = 0; i < X.length(); ++i)
      if (X.charAt(i) != Y.charAt(i) && ++diff > 2)
        return false;
    return true;
  }
}
// code provided by PROGIEZ

839. Similar String Groups LeetCode Solution in Python

class UnionFind {
 public:
  UnionFind(int n) : count(n), id(n), rank(n) {
    iota(id.begin(), id.end(), 0);
  }

  void unionByRank(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
    --count;
  }

  int getCount() const {
    return count;
  }

 private:
  int count;
  vector<int> id;
  vector<int> rank;

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }
};

class Solution {
 public:
  int numSimilarGroups(vector<string>& A) {
    UnionFind uf(A.size());

    for (int i = 1; i < A.size(); ++i)
      for (int j = 0; j < i; ++j)
        if (isSimilar(A[i], A[j]))
          uf.unionByRank(i, j);

    return uf.getCount();
  }

 private:
  bool isSimilar(const string& X, const string& Y) {
    int diff = 0;
    for (int i = 0; i < X.length(); ++i)
      if (X[i] != Y[i] && ++diff > 2)
        return false;
    return true;
  }
};
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents