Java|With detail explaination| O(n^2) O(n^2)
Intuition\nThe solution is actually quite counter-intuitive because most algorithm generates a set of answers based on a few constraints and  do a map-reduce on
# Intuition\nThe solution is actually quite counter-intuitive because most algorithm generates a set of answers based on a few constraints and  do a `map-reduce` onto all the answers (e.g. problem 3 can be seen as generates all subsets and get the number of all subsets), but in this question the constraints are actually too much. Consider this matrix `m`, where `m[i][j] = 0` means `string[i] != string[j]`, vise versa. **We can guarantee that this matrix can instruct us to generate a string, because we know each character\'s equality onto all other characters**, if we also enforce lexicographically smallest, then we have either one possible string or no valid string (which is actually very easy to construct, e.g. `m[i][i] = 0` will lead to a impossible string).\nWith that in mind let\'s look at the `lcp` matrix, apparently this matrix doesn\'t yield more information than the matrix above (there\'s simply no more information to yield anyway), but with the added information it\'s more likely to lead us onto an impossible string. So the idea is really first convert `lcp` onto `m` matrix, construct the only valid string, and then convert back string to `actualLcp` to reverify the original `lcp` is valid or not.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\nO(n^2). It takes O(n^2) to check every index pair and put characters into string, and it takes the same time to get back the `actualLcp` and compare it.`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public String findTheString(int[][] lcp) {\n        char[] resChar = new char[lcp.length];\n\n        // we start with \'a\' which is only valid smallest character to start with.\n        // Now if you think about it, even if the question doesn\'t ask you to get smallest string,\n        // and the OA has a way to verify string result,\n        // starting with \'a\' will still work anyway.\n        for (int i = 0; i < lcp.length; i++) {\n            resChar[i] = \'a\';\n        }\n        for (int i = 0; i < lcp.length; i++) {\n            char c = resChar[i];\n            if (c > \'z\') {\n                return "";\n            }\n            c++;\n            // if string[i] != string[j], make string[j] = string[i] + 1\n            // +1 because we want smallest string\n            for (int j = i; j < lcp.length; j++) {\n                if (lcp[i][j] == 0 && resChar[i] == resChar[j]) {\n                    resChar[j] = c;\n                }\n            }\n        }\n        // we use dynamic programming to get back the actual lcp.\n        // by expanding definition of lcp to include 0 length prefix\n        // we can use formula: lcp[i][j] = 0 if s[i] != s[j]\n        // lcp[i][j] = 1 (expand by 1) + lcp[i + 1][j + 1] vise versa\n        // (which is the lcp value once you remove one more character from\n        // both prefix.)\n        int[][] actualLcp = new int[lcp.length + 1][lcp.length + 1];\n        for (int i = lcp.length - 1; i >= 0; i--) {\n            for (int j = lcp.length - 1; j >= 0; j--) {\n                if (resChar[i] == resChar[j]) {\n                    actualLcp[i][j] = 1 + actualLcp[i + 1][j + 1];\n                }\n                if (actualLcp[i][j] != lcp[i][j]) {\n                    return "";\n                }\n            }\n        }\n        return new String(resChar);\n        \n    }\n}\n```
['Dynamic Programming', 'Java']