C++ | check if possible then construct string greedily.
Intuition\nThere are 4 conditions which must hold true in order for it to be possible.\n\n1. lcp[0][0] must be n.\n2. lcp[i][j] must be same as lcp[j][i].\n3. i
# Intuition\nThere are 4 conditions which must hold true in order for it to be possible.\n\n1. `lcp[0][0]` must be n.\n2. `lcp[i][j]` must be same as `lcp[j][i]`.\n3. if `lcp[i][j]` is more than 0, then `lcp[i + 1][j + 1]` must be `lcp[i][j] - 1`.\n4. `lcp[i][j]` must be less than or equal to `n - max(i, j)`.\n\nIf it meets all these 4 conditions, we start building the string greedily.\n\nAn obsrvation we can make is that if `lcp[i][j]` is more thatn zero, that means that character `i` and `j` should be the same.\n\nfirst we know for sure that the first character should be "a". Then we go through all lcp\'s of the first row, if `lcp[0][j]` is more than zero, that means that there is an "a" at index `j`.\n\nThen we go to the second character in the string. If it is still empty we put in the next minimum available character, which is "b", and we go through all lcp\'s of the second row and fill in every index `j`, where `lcp[1][j]` is more than zero, with "b".\n\nWe continue doing this for every index, checking if it is empty, and if it is empty filling in all index `j`, where `lcp[i][j]` is more than 0, with the next character. If the next character is more than \'z\' we know it\'s impossible.\n\n\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        int n = lcp.size();\n        if (lcp[0][0] < n) return "";\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (lcp[i][j] != lcp[j][i]) return "";\n                if (max(j, i) + lcp[i][j] > n)\n                    return "";\n                if (i && j && lcp[i - 1][j - 1] && lcp[i][j] != lcp[i - 1][j - 1] - 1)\n                    return "";\n            }\n        }\n        string res(n, \' \');\n        char nxt = \'a\';\n        for (int i = 0; i < n; i++) {\n            if (res[i] != \' \') continue;\n            if (nxt > \'z\') return "";\n            for (int j = 0; j < n; j++)\n                if (lcp[i][j]) res[j] = nxt;\n            nxt++;\n        }\n        return res;\n    }\n};\n```
['C++']