Greedy + Z-function
First, we greedily construct our candidate string. Then, we validate that string against the lcp matrix.\n\nFor each position i, we use lcp to check if it match
First, we greedily construct our candidate string. Then, we validate that string against the `lcp` matrix.\n\nFor each position `i`, we use `lcp` to check if it matches any previous character `j`. \n\nIf yes, we use the previous character. If not, we assign the next available character `ch`.\n\n> At this stage, we do not care about repetitions - we only check if `lcp[i][j] > 0`.\n\nFor the validation, we can build an LCP array from the constructed string, and compare it to the input.\n\nNote that the input `lcp` is actually a matrix of Z-functions for each starting position `i`.  Z-function can be computed in O(n).\n\nThere is, however, an easier way to check the matrix. For that, we reverse-engineer how that matrix was populated.\n\nIt was probably populated using DP, and it has a diagonal structure.\n\nIf `lcp[i][j] == k`, then `lcp[i + 1][j + 1] == k -1`, and so on till `lcp[i + k - 1][j + k - 1] == 1`.\n\nTherefore, if `s[i] == s[j]`, then `lcp[i][j] == 1 + lcp[i + 1][j + 1]`.\n\n## Diagonal\n**C++**\n```cpp\nstring findTheString(vector<vector<int>>& lcp) {\n    int n = lcp.size(), ch = \'a\';\n    string res;\n    for (int i = 0; i < n; ++i) {\n        for (int j = 0; j <= i && res.size() == i; ++j)\n            if (lcp[i][j])\n                res.push_back(j < i ? res[j] : ch++);\n        if  (res.back() > \'z\')\n            return "";\n    }\n    for (int i = 0; i < n; ++i)\n        for (int j = 0; j < n; ++j) {\n            int val = res[i] == res[j];\n            if (val && i + 1 < n && j + 1 < n)\n                val += lcp[i + 1][j + 1];\n            if (lcp[i][j] != val)\n                return "";\n        }\n    return res;\n}\n```\n\n## Z-function\n\n**C++**\n```cpp\nvector<int> z_function(string &s, int start) {\n    int n = s.size() - start;\n    vector<int> z(s.size()); \n    for (int i = 1, l = 0, r = 0; i < n; ++i) {\n        if (i <= r)\n            z[i + start] = min(r - i + 1, z[i - l + start]);\n        while (i + z[i + start] < n && s[z[i + start] + start] == s[i + z[ i+ start] + start])\n            ++z[i + start];\n        if (i + z[i+ start] - 1 > r)\n            l = i, r = i + z[i+ start] - 1;\n    }\n    return z;\n}\nstring findTheString(vector<vector<int>>& lcp) {\n    int n = lcp.size(), ch = \'a\';\n    string res;\n    for (int i = 0; i < n; ++i) {\n        for (int j = 0; j <= i && res.size() == i; ++j)\n            if (lcp[i][j])\n                res.push_back(j < i ? res[j] : ch++);\n        if  (lcp[i][i] != n - i || res.back() > \'z\')\n            return "";\n    }\n    for (int i = 0; i < n; ++i) {\n        auto z = z_function(res, i);\n        for (int j = i + 1; j < n; ++j)\n            if (lcp[i][j] != lcp[j][i] || lcp[i][j] != z[j])\n                return "";\n    }  \n    return res;\n}\n```
['C']