Java | DSU | Graph | Full explanation
\nSolution using DSU.\nApproach - \n1. Firt declare parent[], rank[] required for DSU. And fill the default values in them.\n2. Then iterative in lcp[][] for up
\nSolution using DSU.\n**Approach** - \n1. Firt declare parent[], rank[] required for DSU. And fill the default values in them.\n2. Then iterative in lcp[][] for upper j > i region only. Because for i == j, lcp[i][j] == i and lower trianglular values in lcp[][] are same to upper triangular value of lcp[][]. For every lcp[i][j] > 0. Connect position i and j using union() and rank().\n3. Now, we have groups of position in result string str[] with same values.\n4. Iterate from i = 0 to n. Find parent par for position i. If char[par] is 0 then assign it value ++c. Then fill str[i] = chars[par]. By doing that we are filling charater values in possible result string array str[].\n5. Now, we have created str[] but we have not checked whether given lcp[][] is valid or not. So, we will create lcpNew[][] from str[] and match it with given lcp[][]. If lcp[i][j] is not equal to lcpNew[i][j] for any i and j, then return null string.\n6. Create string answer from str[] and return it.\n\nT.C is O(N * N) and S.C is O(N * N)\n\n```\nclass Solution {\n    public String findTheString(int[][] lcp) {\n        int n = lcp.length;\n        int[] parent = new int[n], rank = new int[n], chars = new int[n], str = new int[n];\n        for(int i = 0; i < n; ++i){\n            parent[i] = i;\n            rank[i] = 1;\n        }\n        \n        for(int i = 0; i < n; ++i){\n            for(int j = i + 1; j < n; ++j){\n                if(lcp[i][j] > 0){\n                    union(parent, rank, i, j);\n                }\n            }\n        }\n        \n        int c = 0, par;\n        for(int i = 0; i < n; ++i){\n            par = find(parent, i);\n            if(chars[par] == 0){\n                chars[par] = ++c;\n            }\n            if(c > 26) return ""; // this condition is difficult to think\n            str[i] = chars[par];\n        }\n        // System.out.println(Arrays.toString(str));\n        int val;\n        int[][] lcpNew = new int[n][n];\n        for(int i = n-1; i >= 0; --i){\n            for(int j = n-1; j >= 0; --j){\n                val = (i+1)<n && (j+1)<n ? lcpNew[i+1][j+1] : 0;\n                val = str[i] == str[j] ? 1 + val : 0;\n                lcpNew[i][j] = val;\n                if(lcpNew[i][j] != lcp[i][j]) return "";\n            }\n        }\n        StringBuilder sb = new StringBuilder();\n        for(int e : str){\n            sb.append((char)(e + \'a\' - 1));\n        }\n        return sb.toString();\n    }\n    \n    private int find(int[] parent, int x){\n        if(x == parent[x]) return x;\n        return parent[x] = find(parent, parent[x]);\n    }\n    \n    private void union(int[] parent, int[] rank, int u, int v){\n        u = find(parent, u); v= find(parent, v);\n        if(u == v) return;\n        if(rank[u] >= rank[v]){\n            parent[v] = u;\n            rank[u] += rank[v];\n        }\n        else{\n            parent[u] = v;\n            rank[v] += rank[u];\n        }\n        return;\n    }\n}\n```
['Graph', 'Java']