C++, Simple and Easy Explanation
\n# Complexity\n- Time complexity: O ( N^2 )\n- Space complexity: O ( N^2 )\n Add your space complexity here, e.g. O(n) \n\n# Code\n\n// Class to implement unio
\n# Complexity\n- Time complexity: O ( N^2 )\n- Space complexity: O ( N^2 )\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n// Class to implement union find operations.\nclass UF{\n    public:\n    unordered_map<int, int> rank, parent;\n    void make(int n){\n        for(int i=0; i<n; i++)\n            parent[i] = i;\n    }\n    int find(int n){\n        if(parent[n]!=n)\n            return parent[n] = find(parent[n]);\n        return n;\n    }\n    void merge(int x, int y)\n    {\n        int a = parent[x], b=parent[y];\n        if(a==b)\n            return;\n        if(rank[a]>rank[b])\n            parent[b] = a;\n        else if(rank[a]<rank[b])\n            parent[a] = b;\n        else\n        {\n            parent[a] = b;\n            rank[b]++;\n        }\n    }\n};\n\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& m) {\n        int n = m.size();\n\n        UF u;\n        u.make(n);\n\n        // if m[i][j] > 0, then it means that character i and j are same,\n        // thus putting them in same group using union find class.\n        for(int i=n-1; i>=0; i--)\n        {\n            for(int j=n-1; j>=0; j--)\n            {\n                if(m[i][j])\n                    u.merge(i, j);\n            }\n        }\n        vector<int> v(n, -1);\n        int al = 0;\n\n        // allocating same character to all the element of a group\n        for(int i=0; i<n; i++)\n        {\n            int p = u.find(i);\n            if(v[p]!=-1)\n                v[i] = v[p];\n            else\n            {\n                if(al>=26)\n                    return "";\n                v[i] = al;\n                v[p] = al;\n                al++;\n            }\n        }\n\n        // Check if our found answer can generate the same LCP\n        vector<vector<int>> dp(n, vector<int> (n, 0));\n        for(int i=n-1; i>=0; i--)\n        {\n            for(int j=n-1; j>=0; j--)\n            {\n                if(v[i] == v[j])\n                    dp[i][j] = 1;\n                if(dp[i][j]>0 && i<n-1 && j<n-1)\n                    dp[i][j] += dp[i+1][j+1];\n                if(dp[i][j]!=m[i][j] || v[i]==-1 || v[j]==-1)\n                    return "";\n            }\n        }\n        string s;\n        for(int i=0; i<n; i++)\n            s+=(\'a\'+v[i]);\n        return s;\n    }\n};\n```
['Union Find', 'C++']