[Java/C++/Python] Check Same Characters
Intuition\nIf lcp[i][j] > 0, then A[i] = A[j]\nIf lcp[i][j] == 0, then A[i] != A[j]\n\n\n# Explanation\nWe follow the intution above,\nfind the same A[i] and as
# **Intuition**\nIf `lcp[i][j] > 0`, then `A[i] = A[j]`\nIf `lcp[i][j] == 0`, then `A[i] != A[j]`\n<br>\n\n# **Explanation**\nWe follow the intution above,\nfind the same `A[i]` and assign them to the same character `c`.\nthen construct the whole array `A`.\nWe should use at most 26 different elements.\n\nThen we check if this `A` is valid for `lcp`.\nIf `A[i] == A[j]`,\nthen `lcp[i][j] = lcp[i+1][j+1] + 1`\n\nIf not valid, return empty string.\nIf valid, then we transform `A` to string and return it.\n<br>\n\n# **Complexity**\nTime `O(n^2)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public String findTheString(int[][] lcp) {\n        int n = lcp.length, c = 0, A[] = new int[n];\n        for (int i = 0; i < n; ++i) {\n            if (A[i] > 0) continue;\n            if (++c > 26) return "";\n            for (int j = i; j < n; ++j)\n                if (lcp[i][j] > 0)\n                    A[j] = c;\n        }\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                int v = i + 1 < n && j + 1 < n ? lcp[i + 1][j + 1] : 0;\n                v = A[i] == A[j] ? v + 1 : 0;\n                if (lcp[i][j] != v) return "";\n            }\n        }\n        StringBuilder res = new StringBuilder();\n        for (int a : A)\n            res.append((char)(\'a\' + a - 1));\n        return res.toString();\n    }\n```\n**C++**\n```cpp\n    string findTheString(vector<vector<int>>& lcp) {\n        int n = lcp.size(), c = 0;\n        vector<int> A(n);\n        for (int i = 0; i < n; ++i) {\n            if (A[i]) continue;\n            if (++c > 26) return "";\n            for (int j = i; j < n; ++j)\n                if (lcp[i][j] > 0)\n                    A[j] = c;\n        }\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                int v = i + 1 < n && j + 1 < n ? lcp[i + 1][j + 1] : 0;\n                v = A[i] == A[j] ? v + 1 : 0;\n                if (lcp[i][j] != v) return "";\n            }\n        }\n        string res = "";\n        for (int c : A)\n            res += \'a\' + c - 1;\n        return res;\n    }\n```\n**Python**\n```py\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        n = len(lcp)\n        A = [0] * n\n        c = 1\n        for i in range(n):\n            if A[i]: continue\n            if c > 26: return \'\'\n            for j in range(i, n):\n                if lcp[i][j]:\n                    A[j] = c\n            c += 1\n        for i in range(n):\n            for j in range(n):\n                v = lcp[i + 1][j + 1] if i + 1 < n and j + 1 < n else 0\n                v = v + 1 if A[i] == A[j] else 0\n                if lcp[i][j] != v:\n                    return \'\'\n        return \'\'.join(chr(ord(\'a\') + i - 1) for i in A)\n```\n
['C', 'Python', 'Java']