[C++] Construct and verify O(n^2)
Intuition\nLet\'s construct a solution on the simple requirement:\nif (lcp[i][j] == 0) then // j must be a different letter than i\n\n# Approach\n\nfor (int i =
# Intuition\nLet\'s construct a solution on the simple requirement:\nif (lcp[i][j] == 0) then // j must be a different letter than i\n\n# Approach\n```\nfor (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n```\n\nStep 1) Lets sanity check lcp to begin with.\n\n```\nif (lcp[i][i] != (n - i)) {\n    return "";\n}\n```   \n```\nif (lcp[i][j] != lcp[j][i]) {\n    // lcp needs to be symmetric\n    return "";\n}\n``` \n```\nif (lcp[i][j] > (n - j)) {\n    // the prefix can\'t be longer than [i,n] or [j,n]\n    return "";\n}\n```        \n\nStep 2) Let\'s construct a solution on the simple requirement:\nif (lcp[i][j] == 0) then // j must be a different letter than i\n\nStep 3) After we constructed a solution lets double check if it suffices all requirements from lcp. \n```\nif (ans[i] > \'z\') {\n    return "";\n}\n```\n```\nif (lcp[i][j] != p || lcp[j][i] != p) {\n    // prefix is longer than value specified\n    return "";\n}\n```\n\n\n# Code\n```\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        int n = lcp.size();\n        for (int i = 0; i < n; i++) {\n            if (lcp[i][i] != (n - i)) {\n                return "";\n            }\n        }\n        \n        string ans = string(n, \'a\');\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                if (lcp[i][j] != lcp[j][i]) {\n                    // lcp needs to be symmetric\n                    return "";\n                }\n                if (lcp[i][j] > (n - j)) {\n                    // the prefix can\'t be longer than [i,n] or [j,n]\n                    return "";\n                }\n                if (lcp[i][j] == 0) {\n                    // j must be a different letter than i\n                    if (ans[i] == ans[j]) {\n                        ans[j]++;\n                        if (ans[j] > \'z\') {\n                            // couldn\'t find an english letter to suffice criteria\n                            return "";\n                        }\n                    }\n                }\n            }\n        }\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                int p = 0;\n                int k = i;\n                int l = j;\n                while ((k < n) && (l < n) && ans[k++] == ans[l++]) {\n                    p++;\n                }\n                if (lcp[i][j] != p) {\n                    // prefix is longer than value specified\n                    return "";\n                }\n            }\n        }\n        \n        return ans;\n    }\n};\n```
['C++']