Greedily construct the answer and then check against lcp
Intuition\n Describe your first thoughts on how to solve this problem. \nSuppose string $s$ is the answer and we already know $s[0:j]$ (exclude j, python notati
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSuppose string $s$ is the answer and we already know $s[0:j]$ (exclude j, python notation) then using $lcp[0:j, j]$, we can determine the value of $s[j]$ by (1) setting $s[j] = s[i]$ if $lcp[i][j] > 1$ or (2) setting it to the next unused characters greedily (because the goal is to get the alphabetically smallest string). Eventually, we reconstruct lcp using DP, and compare it against the original lcp array.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n(1) Some initial checks (diagonal elements, symmetry, numerical limitation)\n(2) Build answer greedily (we can also make this algorithm faster by terminating early in this loop)\n(3) Validate lcp array\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(n^2)$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(n^2)$\n\n# Code\n```\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        int n = lcp.size();\n        // check 1: diagonal\n        for (int i = 0; i < n; i++) {\n            if (lcp[i][i] != n - i) return "";\n        }\n        // check 2: limitation and symmetry\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                if (lcp[i][j] > n - j || lcp[i][j] != lcp[j][i]) return "";\n            }\n        }\n        // construct answer\n        string s = string(n, \'#\');\n        s[0] = \'a\';\n        char cur = \'a\';\n        for (int j = 1; j < n; j++) {\n            int i;\n            for (i = 0; i < j; i++) {\n                if (lcp[i][j] > 0) {\n                    s[j] = s[i];\n                    break;\n                }\n            }\n            if (i == j) {\n                if (cur == \'z\') return "";\n                else s[j] = ++cur;\n            }\n        }\n        // check 3: validate lcp\n        int dp[n][n];\n        memset(dp, 0, sizeof(dp));\n        for (int i = n - 1; i >= 0; i--) {\n            if (s[i] == s[n - 1]) dp[i][n - 1] = 1;\n        }\n        for (int j = n - 2; j >= 0; j--) {\n            dp[j][j] = n - j;\n            for (int i = j - 1; i >= 0; i--) {\n                if (s[i] == s[j]) dp[i][j] = 1 + dp[i + 1][j + 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] != dp[i][j]) return "";\n            }\n        }\n        return s;\n    }\n};\n```
['C++']