solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

struct DSU {
    std::vector<int> f;
    DSU(int n) : f(n) { std::iota(f.begin(), f.end(), 0); }
    int leader(int x) {
        if (f[x] == x) {
            return x;
        }
        int y = leader(f[x]);
        f[x] = y;
        return f[x];
    }
    bool merge(int a, int b) {
        auto x = leader(a);
        auto y = leader(b);
        if (x == y) {
            return false;
        }
        f[x] = y;
        return true;
    }
};

class Solution {
   public:
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        DSU dsu(n);

        int m = strs[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cnt = 0;
                vector<int> tmp;
                for (int k = 0; k < m; k++) {
                    if (strs[i][k] != strs[j][k]) {
                        cnt++;
                        tmp.push_back(k);
                    }
                }
                if ((tmp.size() == 2 && strs[i][tmp[1]] == strs[j][tmp[0]]) || tmp.size() == 0) {
                    dsu.merge(i, j);
                }
                
            }
        }

        unordered_set<int> S;
        for (int i = 0; i < n; i++) {
            S.insert(dsu.leader(i));
        }
        return S.size();
    }
};