Simple solution with O(n * n) time complexity and O(n) space complexity
Intuition\n Describe your first thoughts on how to solve this problem. \nBuild the string using partial information in O(n * n), then verify it within O(n * n) 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBuild the string using partial information in O(n * n), then verify it within O(n * n) time complexity\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBuild and verify the string. \n## Pre-verify\nFirst check the lcp given is resonable. Also during the check, for each i, record the info of largest common prefix index and length starting from a smaller index.\n## Try build a smallest string.\nFirstly, if such a string exists, the first character must be \'a.\' Now, suppose we have set the first \'s-1\' characters. To find the character at position \'s\' and beyond, check if there is a substring starting from indices 1, 2, ..., \'s-1\' that has a non-trivial prefix with the substring starting from \'s.\' In other words, look for \'i\' less than \'s\' such that \'lcp[i][s] > 0.\' Any \'i\' will suffice; it\'s not necessary to have the maximal prefix. If there is none, then place a new character that has not been used in the partial string we have built. Otherwise, append characters from \'i\' until the prefix ends. This process always progresses forward, ensuring it will eventually end.\n## Post verify\nThe process we described only uses partial information, so the resulting string is not always valid. We need to check its validity.\n\nA simple way to check is for each \'i < j,\' verify that they have the desired prefix length. However, the relationship between \'lcp[i][j]\' and \'lcp[i+1][j+1]\' is intertwined, so checking the first character of the prefix is sufficient.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n * n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n\n# Code\n```\nusing namespace std;\n\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        const int n = lcp.size();\n        std::vector<std::pair<int, int>> repeat_index(n, {-1, 0}); \n        for (int i = 0; i < n; ++i) {\n            if (lcp[i][i] != n - i) {\n                return {};\n            }\n            for (int j = i + 1; j < n; ++j) {\n                if (lcp[i][j] != lcp[j][i]) {\n                    return {};\n                }\n                if (lcp[i][j] > repeat_index[j].second) {\n                    repeat_index[j] = {i, lcp[i][j]};\n                }\n            }\n        }\n\n        auto len = 1;\n        string ret {"a"};\n        ret.reserve(n);\n        char highest_char = \'a\';\n        while (len < n) {\n            const auto [j, repeat] = repeat_index[len];\n            if (repeat == 0) {\n                highest_char++;\n                if (highest_char > \'z\') {\n                    return {};\n                }\n                ret.push_back(highest_char);\n                ++len;\n            } else {\n                for (int i = j; i < j + repeat; ++i) {\n                    ret.push_back(ret[i]);\n                }\n                len += repeat;\n            }\n        }\n\n        if (len > n) {\n            return {};\n        } else {\n            for (int i = 0; i < n; ++i) {\n                for (int j = 0; j < i; ++j) {\n                    auto repeat = lcp[i][j];\n                    bool invaild = repeat > 0 && ret[i] != ret[j];\n                    invaild |= ret[i + repeat] == ret[j + repeat];\n                    if (invaild) {\n                        return {};\n                    }\n                }\n            }\n            return ret;\n        }\n    }\n};\n```
['C++']