UNION FIND SOLUTION || C++ || SIMPLE || ELABORATIVE
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nThere are lot of condit
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThere are lot of conditions to be verified. \n1. All the diagonals elements should be in decreasing order n,n-1,n-2,...,1\n2. The trasition of (i,j) from (i+1,j+1) differs by 1 because adding 1 character can increase the same prefix by at most one.\n3. Characters required must be in range [a-z]  \n\n# Complexity\n- Time complexity: O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass DSU{\n   public:\n    vector<int> parent,size; \n    DSU(int n)\n    {\n        parent.resize(n);\n        size.resize(n,1);\n        for(int i=0;i<n;i++)\n            parent[i] = i;\n    }\n    int find(int n)\n    {\n        if(parent[n]!=n)\n            return parent[n] = find(parent[n]);\n        return n;\n    }\n    void Union(int x,int y)\n    {\n        int u = find(x);\n        int v = find(y);\n        if(u!=v)\n        {\n            if(size[u]>size[v])\n            {\n                parent[v] = u;\n                size[u]+=size[v]; \n            }\n            else\n            {\n                parent[u] = v;\n                size[v]+=size[u];\n            }\n        }\n    }\n};\n\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        int n = lcp.size();\n        vector<int> dp(n,-1);\n        for(int i=0;i<n;i++)\n            for(int j=0;j<n;j++)\n            {\n                if(lcp[i][j]!=lcp[j][i] || lcp[i][j] > n - i || lcp[i][j] > n-j) return "";\n                if(i==j && lcp[i][j]!= n-i) return "";\n                if(i<n-1 && j<n-1 && lcp[i][j]!=0 && lcp[i][j]==lcp[i+1][j+1]) return "";\n            }\n        DSU d(n);\n        for(int i=n-1;i>=0;i--)\n        {\n            for(int j=i;j>=0;j--)\n            {\n                if(lcp[i][j]==1)\n                {\n                    int l =i,r=j;\n                    d.Union(l,r);\n                    while(l>0 && r>0 && lcp[l-1][r-1] == lcp[l][r]+1)\n                    {\n                        l--;\n                        r--;\n                        d.Union(l,r);\n                    }\n                }\n                if(i>0 && j>0 && lcp[i-1][j-1] > lcp[i][j]+1)\n                        return "";\n                if(lcp[i][j]==0)\n                {\n                    if(d.find(i) == d.find(j))\n                        return "";\n                }\n            }\n        }\n        map<int,char> mapping;\n        char c = \'a\';\n        string ans(n,\'#\');\n        for(int i=0;i<n;i++)\n        {\n            int p = d.find(i);\n            if(mapping.find(p)==mapping.end())\n                mapping[p] = c++;\n            if(c == \'z\'+2)\n                return "";\n            ans[i] = mapping[p];\n        }\n        return ans;\n    }\n};\n```
['C++']