2573. Find the String with LCP using Python3
Intuition\n Describe your first thoughts on how to solve this problem. \nAssign lexicographically smallest characters based on the LCP matrix and validate suffi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**Assign lexicographically smallest characters based on the LCP matrix and validate suffix consistency efficiently using the Z-function.** I have included comments in the program for a better understanding.\n\n# HINTS\nFor each suffix of the constructed string, calculate the Z-function and compare it with the corresponding row in the LCP matrix to ensure correctness.\n\nReuse precomputed values instead of recalculating lcp[i][j] or other comparisons repeatedly.\n\n# Complexity\n- Time complexity:O(n^2) \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: o(n) -for storing the z_array and the constructed string.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def calculateZFunction(self, string):\n        """\n        Computes the Z-function for the given string.\n        Z[i] represents the length of the longest common prefix starting at index i\n        with the prefix of the string.\n        """\n        n = len(string)\n        z_array = [0] * n\n        left, right = 0, 0\n        for i in range(1, n):\n            if i <= right and z_array[i - left] < right - i + 1:\n                z_array[i] = z_array[i - left]\n            else:\n                z_array[i] = max(0, right - i + 1)\n                while i + z_array[i] < n and string[z_array[i]] == string[i + z_array[i]]:\n                    z_array[i] += 1\n            if i + z_array[i] - 1 > right:\n                left, right = i, i + z_array[i] - 1\n\n        z_array[0] = n  # The entire string matches itself at index 0\n        return z_array\n\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        """\n        Constructs the lexicographically smallest string based on the LCP matrix.\n        Returns an empty string if it\'s not possible to construct such a string.\n        """\n        n = len(lcp)\n        constructed_string = [\'\'] * n  # Placeholder for the resulting string\n        next_char_index = 0  # To assign lexicographically smallest characters\n\n        # Step 1: Assign characters based on LCP matrix\n        for i in range(n):\n            # If diagonal check fails, it\'s invalid\n            if i + lcp[i][i] != n:\n                return \'\'\n\n            # Assign a new character if not yet assigned\n            if constructed_string[i] == \'\':\n                if next_char_index > 25:  # Out of characters (\'a\' to \'z\')\n                    return \'\'\n                constructed_string[i] = chr(ord(\'a\') + next_char_index)\n                next_char_index += 1\n\n            # Propagate the character to other indices based on LCP constraints\n            for j in range(i + 1, n):\n                if lcp[i][j] != lcp[j][i]:  # Symmetry check\n                    return \'\'\n                if lcp[i][j]:  # If there\'s a common prefix\n                    if constructed_string[j] != \'\' and constructed_string[j] != constructed_string[i]:\n                        return \'\'  # Conflict detected\n                    constructed_string[j] = constructed_string[i]\n\n        # Step 2: Validate the constructed string using the Z-function\n        constructed_string = \'\'.join(constructed_string)\n        for i in range(n):\n            suffix_z = self.calculateZFunction(constructed_string[i:])\n            if suffix_z != lcp[i][i:]:\n                return \'\'\n\n        return constructed_string\n\n```
['Python3']