Java | Union Find
Code\n\nclass Solution {\n    class DSU {\n        public int[] roots;\n        public int[] sizes;\n        DSU(int n) {\n            roots = new int[n];\n    
# Code\n```\nclass Solution {\n    class DSU {\n        public int[] roots;\n        public int[] sizes;\n        DSU(int n) {\n            roots = new int[n];\n            sizes = new int[n];\n            for (int i = 0; i < n; i++) {\n                roots[i] = i;\n                sizes[i] = 1;\n            }\n        }\n\n        public int find(int a) {\n            int rootA = roots[a];\n            if (a == rootA) {\n                return a;\n            }\n            roots[a] = find(roots[a]);\n            return roots[a];\n        }\n\n        public void union(int a, int b) {\n            int rootA = find(a);\n            int rootB = find(b);\n            if (rootA == rootB) {\n                return;\n            }\n\n            if (sizes[rootA] > sizes[rootB]) {\n                roots[rootB] = rootA;\n                sizes[rootA] += sizes[rootB];\n            } else {\n                roots[rootA] = rootB;\n                sizes[rootB] += sizes[rootA];\n            }\n        }\n    }\n    public String findTheString(int[][] lcp) {\n        int n = lcp.length;\n        \n        DSU dsu = new DSU(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                    dsu.union(i, j);\n                }\n            }\n        }\n        char c = \'a\';\n        char[] ch = new char[n];\n        \n        for (int i = 0; i < n; i++) {\n            int root = dsu.find(i);\n            if (ch[root] == 0) {    \n                if (c > \'z\') {\n                    return "";\n                }\n                ch[root] = c;\n                c++;                \n            }\n            ch[i] = ch[root];\n        }\n        for (int start = n-1; start >= 0; start--) {\n            int i = start;\n            int j = n-1;\n            while (i >= 0 && j >= 0) {\n                int cnt = (ch[i] == ch[j]) ? 1 : 0;\n                if (j < (n-1) && cnt > 0) {\n                    cnt += lcp[i+1][j+1];\n                }\n                if (lcp[i][j] != cnt || lcp[j][i] != cnt) {\n                    return "";\n                }\n                i--;\n                j--;\n            }\n        }\n        return String.valueOf(ch);\n    }\n}\n```
['Java']