C++ Fast O(N^2), using Generative algorithm, build candidate then verify
Approach:\n Initially, we have n a as the initial candidate string\n we use each row of lcp matrix to determine if we should bump the character up\n if lcp[r][c
Approach:\n* Initially, we have `n` `a` as the initial candidate string\n* we use each row of `lcp` matrix to determine if we should bump the character up\n* if `lcp[r][c]` == `0`, and the char do not equal, then we must increase it to the next available char.\n* If any char is beyond `z`, then we return impossible.\n\nThen, we calculate the would be `lcp` as the `would` matrix, using Dynamic Programming.\nComparing that with the original `lcp`, and if they are inconsistent. return impossible.\n\nOtherwise, we return the built `cand` string.\n\n```c++\nclass Solution {\n public:\n  string findTheString(vector<vector<int>> &lcp) {\n    const int n = lcp.size();\n    string cand = "";\n    for (int i = 0; i < n; i++)\n      cand += "a";\n    // now we have cand as a string of length n with all a\'s\n\n    for (int r = 0; r < n; r++) {\n      for (int c = r; c < n; c++) {\n        if (lcp[r][c] == 0 && cand[c] == cand[r])\n          cand[c]++; // lcp is 0, and the chars equal, bump it up\n      }\n    }\n\n    // if the cand string is beyond `z`, then impossible.\n    for (char ch : cand)\n      if (ch > \'z\')\n        return "";\n\n    // using DP to build the would lcp matrix\n    int would[n + 1][n + 1];\n    memset(would, 0, sizeof(would));\n    for (int r = n - 1; r >= 0; r--) {\n      for (int c = n - 1; c >= 0; c--) {\n        if (cand[r] == cand[c]) {\n          would[r][c] = 1 + would[r + 1][c + 1];\n        }\n      }\n    }\n\n    // the `would` matrix we built, must equal to the original matrix given by the problem.\n    for (int r = 0; r < n; r++)\n      for (int c = 0; c < n; c++)\n        if (would[r][c] != lcp[r][c])\n          return "";\n\n    return cand;\n  }\n};\n```
['Dynamic Programming', 'C']