[Python3] Union find solution
Intuition\n Describe your first thoughts on how to solve this problem. \nUnion find structure helps a lot with combining the same chars and then checking for co
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUnion find structure helps a lot with combining the same chars and then checking for contradictions.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nStep 1: Use rules from lcp array to unify same symbols. Simultaneously checking for inconsistencies.\nStep 2: Check all conditions fulfilled and self-consistent.\nStep 3: Use union find structure to fill answer with chars.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space 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        uf = [i for i in range(n)]\n        \n        def find(x):\n            if uf[x] == x:\n                return x\n            uf[x] = find(uf[x])\n            return uf[x]\n        \n        #  Step 1: Use rules from lcp array to unify same symbols. Simultaneously checking for inconsistencies.\n        for i in range(n):\n            # bc symbols are equal to themselves\n            if lcp[i][i] + i != n:\n                return ""\n            for j in range(i + 1, n):\n                # border and symmetry check\n                if j + lcp[i][j] > n or lcp[i][j] != lcp[j][i]:\n                    return ""\n                \n                if lcp[i][j]:\n                    if j + 1 < n and lcp[i + 1][j + 1] + 1 != lcp[i][j]:\n                        return ""\n        \n                    uf[i] = uf[j] = min(find(i), find(j))\n                    \n        #  Step 2: Check all conditions fulfilled and self-consistent.\n        for i in range(n):\n            for j in range(i + 1, n):\n                # cases: need to be unequal, but in reality opposite\n                if lcp[i][j] == 0 and find(i) == find(j):\n                    return ""\n                if lcp[i][j] > 0 and lcp[i][j] + j < n and find(i + lcp[i][j]) == find(j + lcp[i][j]):\n                    return ""\n                \n        #  Step 3: Use union find structure to fill answer with chars.\n        ret = [None] * n\n        letter = 97  # ASCII code of \'a\' letter\n        for i in range(len(ret)):\n            val = find(i)\n            if ret[val] is not None:\n                ret[i] = ret[val]\n            else:\n                # if needed more letters, we can\'t afford it, as \'z\' has 122 ASCII code\n                if letter == 123:\n                    return ""\n                ret[i] = chr(letter)\n                letter += 1\n        return \'\'.join(ret)\n        \n```
['Union Find', 'Python3']