Python Solution with Video Explanation
Detailed Video explanation:\n\nhttps://youtu.be/11VXS2Vbv3s\n\n# Intuition\nBuild the string first then validate.\n\n# Approach\n- build the string using lcp fi
**Detailed Video explanation:**\n\nhttps://youtu.be/11VXS2Vbv3s\n\n# Intuition\nBuild the string first then validate.\n\n# Approach\n- build the string using lcp first by assing smallest lowercase char first \n- validate the string using lcp matrix\n- lcp[i][j] must equal lcp[i+1][j+1] + 1 if (i, j) shares common prefix\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\n        # build s\n        s = [\'\' for _ in range(n)]\n        c = \'a\' # \'a\' .... \'z\'\n        for i in range(n):\n            if s[i] != \'\':\n                continue\n            if c > \'z\': \n                return ""\n            s[i] = c\n            for j in range(n):\n                if lcp[i][j] > 0: # len(common_prefix(s[i:] , s[j:])) > 0\n                    s[j] = s[i] \n            c = chr(ord(c) + 1)\n\n        print("".join(s))\n\n        # validate last column and last row\n        for i in range(n):\n            if lcp[i][n - 1] != (s[i] == s[n-1]):\n                return ""\n            if lcp[n-1][i] != (s[i] == s[n-1]):\n                return ""\n\n        # validate rest of lcp: if s[i] == s[j] => lcp[i][j] = 1 + lcp[i+1][j+1]\n        for i in range(n-1):\n            for j in range(n-1):\n                if s[i] == s[j]:\n                    if lcp[i][j] != 1 + lcp[i+1][j+1]: \n                        return ""\n                else: # char at i and j are different => lcp[i][j] should be 0\n                    if lcp[i][j] != 0:\n                        return ""\n\n        return "".join(s)\n\n```
['Python3']