Simple and Intuitive Java Solution using Disjoint Set Union (Union Find)
Intuition\nif lcp[i][j] is > 0, then the substring (i, i+lcp[i][j]-1) equals (j, j+lcp[i][j]-1). This also means that character i+lcp[i][j] is not equal to j+lc
# Intuition\nif lcp[i][j] is > 0, then the substring (i, i+lcp[i][j]-1) equals (j, j+lcp[i][j]-1). This also means that character i+lcp[i][j] is not equal to j+lcp[i][j]. We can use disjoint set union to mark when 2 characters are equal.\n\n# Approach\nWe actually don\'t need to make sure that every substring that we know is the same is actually the same in dsu, only the first character. This is because if lcp[i][j] > 0 then lcp[i+1][j+1] = lcp[i][j]-1. This means when we go to position lcp[i+1][j+1] in the loop we are checking the second character in the same substring, so we don\'t need to do it the first time. We only need to unite characters i and j if lcp[i][j] > 0 to signify that they are the same. After that we need to make sure that i+lcp[i][j] is not the same as j+lcp[i][j]. Then, if the number of connected components in disjoint set union (witch is the same as the number of distinct charaters) is > 26 it is impossible. So we can simply just go through each character, and assign the first connected components to the lowest possible characters to make the string lexographically the shortest (since this means we prioritize making the first characters smaller instead of the last characters).\n\nNote that we are using DSU for distinct characters. if a and b are in the same connected component, they are the same character. Otherwise they are different characters.\n\n# Complexity\n- Time complexity:\nO(N^2 logN)\n\n- Space complexity:\nO(N^2)\n\n# Code\n```\nclass Solution {\n    public String findTheString(int[][] lcp) {\n        int n = lcp.length;\n        DSU d = new DSU(n);\n        for(int i = 0; i<n; i++) for(int j = 0; j<n; j++) if(lcp[i][j] != 0){\n            d.unite(i, j);\n            if(i != n-1 && j != n-1 && lcp[i+1][j+1] != lcp[i][j]-1) return "";\n        }\n        for(int i = 0; i<n; i++) for(int j = 0; j<n; j++){\n            int a = i+lcp[i][j], b = j+lcp[i][j];\n            if(a > n || b > n) return "";\n            if(a != n && b != n && d.isSame(a, b)) return "";\n        }\n        if(d.getCC() > 26) return "";\n        Map<Integer, Character> map = new HashMap<>();\n        char last = \'a\';\n        StringBuilder sb = new StringBuilder();\n        for(int i = 0; i<n; i++){\n            Character get = map.get(d.get(i));\n            if(get == null)\n                map.put(d.get(i), get = last++);\n            sb.append(get);\n        }\n        return sb.toString();\n    }\n\tprivate static class DSU {\n\t\tprivate int[] par, size;\n\t\tprivate int cc;\n\n\t\tpublic DSU(int N) {\n\t\t\tpar = new int[N];\n\t\t\tsize = new int[N];\n\t\t\tcc = N;\n\t\t\tArrays.fill(par, -1);\n\t\t\tArrays.fill(size, 1);\n\t\t}\n\n\t\tpublic int size(int num) {\n\t\t\treturn size[get(num)];\n\t\t}\n\n\t\tpublic int get(int num) {\n\t\t\treturn par[num] == -1 ? num : (par[num] = get(par[num]));\n\t\t}\n\n\t\tpublic boolean isSame(int x, int y) {\n\t\t\treturn get(x) == get(y);\n\t\t}\n\n\t\tpublic boolean unite(int x, int y) {\n\t\t\tint p1 = get(x), p2 = get(y);\n\t\t\tif (p1 == p2)\n\t\t\t\treturn false;\n\t\t\tif (size[p1] < size[p2]) {\n\t\t\t\tint s = p2;\n\t\t\t\tp2 = p1;\n\t\t\t\tp1 = s;\n\t\t\t}\n\t\t\tsize[p1] += size[p2];\n\t\t\tpar[p2] = p1;\n\t\t\tcc--;\n\t\t\treturn true;\n\t\t}\n\n\t\tpublic int getCC() {\n\t\t\treturn cc;\n\t\t}\n\t}\n}\n```
['Union Find', 'Java']