[Python3] O(n^2) Build string from left to right and z-function check LCP
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst we build s from left to right. For position i, we will fill it with current small
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst we build s from left to right. For position i, we will fill it with current smallest char if it is empty. Next we will check lcp with all other substrings starting with i+1, i+2, ..., n-1. If lcp[i][j] > 0, it means s[j] == s[i]. \nRepeat this process we will always get a string. Then we use z-function to check the lcp matrix. The detail of z-function please refer to [https://cp-algorithms.com/string/z-function.html](https://cp-algorithms.com/string/z-function.html).\n\n**Notice:**\n1. The lcp matrix is symmetric. The diagonal element is same as the substring length.\n2. Make sure the chars we used are not exceed 26.\n\n\n# Code\n```\nclass Solution:\n    def z_function(self, s):\n        n = len(s)\n        z = [0] * n\n        l, r = 0, 0\n        for i in range(1, n):\n            if i <= r and z[i - l] < r - i + 1:z[i] = z[i - l]\n            else:\n                z[i] = max(0, r - i + 1)\n                while i + z[i] < n and s[z[i]] == s[i + z[i]]:z[i] += 1\n            if i + z[i] - 1 > r:\n                l = i\n                r = i + z[i] - 1\n        z[0] = len(s)\n        return z\n\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        n = len(lcp)\n        s, idx = [\'\'] * n, 0\n        for i in range(n):\n            if i + lcp[i][i] != n: return \'\'\n            if s[i] == \'\':\n                if idx > 25: return \'\'\n                s[i] = chr(ord(\'a\') + idx)\n                idx += 1\n            for j in range(i + 1, n):\n                if lcp[i][j] != lcp[j][i]: return \'\'\n                if lcp[i][j]:\n                    if s[j] != \'\' and s[j] != s[i]: return \'\'\n                    s[j] = s[i]\n        s = \'\'.join(s)\n        return \'\' if any(self.z_function(s[i:]) != lcp[i][i:] for i in range(n)) else s\n```
['Python3']