O(n^2) solution explained | Python
Intuition\nOne way to solve this problem is to reverse-engineer the string from the given LCP matrix.\n\n# Approach\n1. Check top-left to bottom-right diagonal.
# Intuition\nOne way to solve this problem is to reverse-engineer the string from the given LCP matrix.\n\n# Approach\n1. Check top-left to bottom-right diagonal. They should be in strictly decreasing order from n -> 1.\n2. Reverse engineer the string. Att each position:\n    - If the position has been filled, that means if there is any position after the current position that needs to be the same as the current position, it should be already filled too with the same character.\n    - If the position has not been filled, We fill the position with the next available character `curr_l` and all the positions after that, that have to be the same as curr position.\n3. This step would be kind of DP, but instead of filling in values, we check the values.\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        n = len(lcp)\n        letters = [None] * n\n        curr_l = \'a\'\n        \n        for i in range(n):\n            if lcp[i][i] != n-i: return ""\n            lcp[i].append(0)\n        \n        for i in range(n):\n            l = letters[i]\n            if l is not None:\n                for j in range(i+1, n):\n                    if lcp[i][j] != lcp[j][i]: return ""\n                    if lcp[i][j] and letters[j] != l: return ""\n            else:\n                if curr_l > \'z\': return ""\n                for j in range(i, n):\n                    if lcp[i][j] != lcp[j][i]: return ""\n                    if lcp[i][j]:\n                        if letters[j]:\n                            if letters[j] != curr_l: return ""\n                        else:\n                            letters[j] = curr_l\n                curr_l = chr(ord(curr_l) + 1)\n                \n            \n        for i in range(n-1):\n            for j in range(i+1, n):\n                if letters[i] == letters[j] and lcp[i][j]!=lcp[i+1][j+1]+1:\n                    return ""\n        \n        \n        return \'\'.join(letters)\n                \n```
['Python3']