Disjoint Set Union, Beats 100% of submissions
Intuition\n Describe your first thoughts on how to solve this problem. \nProblem constraints are like DSU may not be be the best idea to solve it. But DSU solut
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nProblem constraints are like DSU may not be be the best idea to solve it. But DSU solution may work equally well for n being 10^5. Each component of size k may require k/2 operations:\na-> 0\naa-> 1 (ac)\naaa-> 1 (aca)\naaaa-> 2 (acac)\naaaaa-> 2 (acaca)\n.......\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe iterate over each character and do union operation with the left and right characters if the absolute difference between the ASCII values is less than or equal to 1. Then we iterate over the elements of the DSU array to get the components size from the root node and increment componentSize/2 to the result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n*\u03B1(n))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass UnionFind\n{\n    public:\n    vector<int> id, sz;\n    UnionFind(int n) : id(vector<int>(n)), sz(vector<int>(n, 1))\n    {\n        iota(id.begin(), id.end(), 0);\n    }\n    int find(int p)\n    {\n        int root = id[p];\n        while(root != id[root]) root = id[root];\n        while(root != p)\n        {\n            int k = id[p];\n            id[p] = root;\n            p = k;\n        }\n        return root;\n    }\n    void getUnion(int p, int q)\n    {\n        int root1 = find(p);\n        int root2 = find(q);\n        if(root1 == root2) return;\n        if(sz[root1] > sz[root2])\n        {\n            id[root2] = root1;\n            sz[root1] += sz[root2];\n        }\n        else\n        {\n            id[root1] = root2;\n            sz[root2] += sz[root1];\n        }\n    }\n};\nclass Solution {\npublic:\n    int removeAlmostEqualCharacters(string word) {\n        int n = word.length();\n        UnionFind obj(n);\n        for(int i = 0; i < n; i++)\n        {\n            if(i+1 < n && abs(word[i+1] - word[i]) <= 1) obj.getUnion(i, i+1);\n            if(i-1 >= 0 && abs(word[i-1] - word[i]) <= 1) obj.getUnion(i, i-1);\n        }\n        int res = 0;\n        for(int i = 0; i < n; i++)\n            if(obj.id[i] == i) res += obj.sz[i] / 2;\n        return res;\n    }\n};\n```
['C++']