[Python3] Simple and commented O(N^2)
Code\n\nclass Solution:\n\n    def checkNewLCP(self, lcp: List[List[int]], output: List[str]) -> bool:\n        n = len(output)\n        for row_index in range(
# Code\n```\nclass Solution:\n\n    def checkNewLCP(self, lcp: List[List[int]], output: List[str]) -> bool:\n        n = len(output)\n        for row_index in range(n):\n            for col_index in range(n):\n                prev_val = lcp[row_index+1][col_index+1] if (row_index+1 < n and col_index+1 < n) else 0\n                expected_val = -1\n                if output[col_index] == output[row_index]:\n                    # If the two chars match, it means they must extend the prefix of lcp[row_index+1][col_index+1] by one because we have an additional matching char in both substrings\n                    expected_val = prev_val + 1\n                else:\n                    # Since the additional char in the two substrings does not match, I expect the prefix to become zero\n                    expected_val = 0\n                if lcp[row_index][col_index] != expected_val:\n                    return False\n        return True\n\n    def checkOldLCP(self, lcp: List[List[int]]) -> bool:\n        n = len(lcp)\n        for row_index in range(n):\n            for col_index in range(n):\n                if row_index == col_index:\n                    # Check if the value is the expected one\n                    expected_value = n - row_index\n                    if lcp[row_index][col_index] != expected_value:\n                        return False\n                if lcp[row_index][col_index] != lcp[col_index][row_index]:\n                    return False\n                # Check the length of the two string\n                if lcp[row_index][col_index] > n - max(row_index, col_index):\n                    return False\n        return True\n\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        # Check if the matrix is symmetric and if in its principal diagonal we have the series [N, ..., 1]\n        n = len(lcp)\n        if not self.checkOldLCP(lcp):\n            return ""\n        \n        output = [\'$\'] * n\n        current_letter_index = 0\n\n        for row_index in range(n):\n            for col_index in range(row_index, n):\n                # If a letter has not been assigned to this position, assign it\n                if output[row_index] == \'$\':\n                    # If we ran out of letters, then we cannot build this string\n                    if ord(\'a\') + current_letter_index > ord(\'z\'):\n                        return ""\n                    output[row_index] = chr(ord(\'a\') + current_letter_index)\n                    current_letter_index += 1\n\n                assert output[row_index] != \'$\'\n                if lcp[row_index][col_index] == 0:\n                    # Rule: The two positions must not match\n                    if output[row_index] == output[col_index]:\n                        return ""\n                else:\n                    # Rule: The two positions must match\n\n                    # if there is already a character assigned to the "col_index" position, it must have been assigned by another rule, so there\'s a mismatch between rules => return empty string\n                    if output[col_index] != \'$\':\n                        if output[col_index] != output[row_index]:\n                            return ""\n                        else:\n                            # The two positions already match, so nothing to do\n                            pass\n                    else:\n                        # Assign the character in row_index position to the col_index position as dictated by the rule\n                        output[col_index] = output[row_index]\n        \n        if not self.checkNewLCP(lcp, output):\n            return ""\n        else:\n            return "".join(output)\n```
['Python3']