O(N^2) Solution in Python, Faster than 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe basic rule is as simple as lcp[i][j] > 0 if and only if s[i] == s[j].\n\n# Approach
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe basic rule is as simple as `lcp[i][j] > 0` if and only if `s[i] == s[j]`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAssign the same character to both `i` and `j` if `lcp[i][j] > 0`. Check for the inconsistancies. \nAs we traverse the characters in the increasing order, the union and find can be done by the greedy assignment in $O(1)$. No disjoint set, which is slower than $O(1)$, is required.\n\n\n# Complexity\n- Time complexity: $O(N^2)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        n = len(lcp)\n        max_alpha = ord(\'a\')\n        groups = list(range(n))\n        not_equal = []\n        for i in range(n):\n            if lcp[i][i] != n - i:\n                return ""\n            for j in range(i + 1, n):\n                if lcp[i][j] != lcp[j][i]:\n                    return ""\n                if i > 0 and ((lcp[i-1][j-1] > 0 and lcp[i][j] != lcp[i-1][j-1] - 1)):\n                    return ""\n                if lcp[i][j] > n - i or lcp[i][j] > n - j:\n                    return ""\n                if lcp[i][j] > 0:\n                    if groups[j] != j and groups[j] != groups[i]:\n                        return ""\n                    groups[j] = groups[i]\n                else:\n                    not_equal.append((i, j))\n        assignments = {}\n        s = []\n        for v in groups:\n            if v not in assignments:\n                assignments[v] = chr(max_alpha)\n                if not assignments[v].isalpha():\n                    return ""\n                max_alpha += 1\n            s.append(assignments[v])\n        if any(s[i] == s[j] for i, j in not_equal):\n            return ""        \n        return "".join(s)\n```
['String', 'Greedy', 'Union Find', 'Python3']