C++, O(N^2), easy explanation
\n\t[[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]\n1. string is of length n, in this case 4 ("####")\n2. for a particular index j in this string s we check all its 
\n\t[[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]\n1. string is of length n, in this case 4 ("####")\n2. for a particular index j in this string s we check all its previous characters( i : j-1 -> 0)\n   to check for common prefix\n    if(lcp[i][j] > 1) it means that they have a common prefix or we can say s[j] == s[i];\n    if(lcp[i][j] == 0) it means that they have no common prefix so we can say that s[j] cannot be     s[i] for this we create an invalid array of char so that after traversing from i: j-1 -> 0 we       can find that lexicographically smallest char that we can insert is no char that we return "";\n3. after creating the string s we check if the lcp matrix is valid from the generated string \n```\n  0,1,2,3\n0[4,0,2,0],\n1[0,3,0,1],\n2[2,0,2,0],\n3[0,1,0,1],\n\nj = 0, c(char to be inserted at j) = \'$\'(initially)\n    i = -1 exit i loop \n    since c == \'$\' first valid char that can be inserted \'a\' so c = \'a\'\ns = "a"\n\nj = 1, c = \'$\'\n    i = 0 \n        lcp[i][j] == 0 no prefix or s[j] cannot be s[i] therefore invalid[s[i]] = 1;\n    i = -1 exit i loop \n    since c == \'$\' first valid char that can be inserted \'b\' so c = \'b\'\ns = "ab"\n\nj = 2, c = \'$\'\n    i = 1\n        lcp[i][j] == 0 no prefix or s[j] cannot be s[i] therefore invalid[s[i]] = 1;\n    i = 0 \n        lcp[i][j] > 1 common prefix or s[j] = s[i] therefore c = s[i];\n    i = -1 exit i loop \n    since c != \'$\' we push c(a)\ns = "aba"\n\nj = 3, c = \'$\'\n    i = 2\n        lcp[i][j] == 0 no prefix or s[j] cannot be s[i] therefore invalid[s[i]] = 1;\n    i = 1\n        lcp[i][j] > 1 common prefix or s[j] = s[i] therefore c = s[i];\n    i = 0\n        lcp[i][j] == 0 no prefix or s[j] cannot be s[i] therefore invalid[s[i]] = 1;\n    i = -1 exit i loop \n    since c != \'$\' we push c(b)\ns = "abab"\n```\n4. for checking LCP matrix through generated string through bottom up dp\n   s = "abab" ||  i : n-1 -> 0 || j : n-1 -> 0\n   general idea: \n       if(s[i] == s[j]) then longest common prefix will be lcp of (s[i+1]&s[j+1])+1\n       lcp[i][j] must lcp[i+1][j+1]+1 if s[i] == s[j]\n\n```\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        int n = lcp.size(),v;\n        string res = ""; vector<int> invalid;\n        for(int j=0; j<n; ++j){\n            invalid = vector<int>(26,0);\n            char c = \'$\';\n            for(int i=j-1; i>=0; --i){\n                if(lcp[i][j] > 0){\n                    if(c != \'$\' && c != res[i]) return "";\n                    else c = res[i];\n                }else{\n                    invalid[res[i]-\'a\'] = 1;\n                }\n            }\n            if(c == \'$\'){\n                for(int k=0; k<26; ++k){\n                    if(!invalid[k]){\n                        c = \'a\'+k; break;\n                    }\n                }\n                if(c == \'$\') return "";\n            }\n            res.push_back(c);\n        }\n        \n        for(int i=n-1; i>=0; --i){\n            for(int j=n-1; j>=0; --j){\n                v = 0;\n\t\t\t\t// (i+1 == n || j+1 == n)  check for out of bounds\n                if(res[i] == res[j]) v = (i+1 == n || j+1 == n) ? 1 : lcp[i+1][j+1]+1;\n                if(lcp[i][j] != v) return "";\n            }\n        }\n        return res;\n    }\n};\n```
['Dynamic Programming', 'Greedy', 'C']