Greedy construction
Intuition\nFor every position in the string, what is the minimum character which can be used to fill that position without violating any previous conditions.\n\
# Intuition\nFor every position in the string, what is the minimum character which can be used to fill that position without violating any previous conditions.\n\n\n# Approach\n\nConstruct a directed graph where an edge between i and j denotes that S[i] != S[j]. For each lcp element, the first smallest index where the two substrings are unequal contribute to the edges of this graph. From this graph, for each position, find the min c such no conditions are violated.\n\nFinally reconstruct the lcp array using dynamic programming and ensure it is equal to the given lcp. If so return the greedily constructed string.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n^2)$$\n\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> E[1111];\n    string findTheString(vector<vector<int>>& lcp) {\n        int n=lcp.size();\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]) return "";\n                int l2=n-j;\n                if (j+lcp[i][j]<n) {\n                    E[j+lcp[i][j]].push_back(i+lcp[i][j]);\n                }\n            }\n        }\n        \n        \n        string S(n,\'#\');\n        for(int i=0;i<n;i++) {\n            int mask=0;\n            for(int j : E[i]) {\n                mask|=(1<<(S[j]-\'a\'));\n            }\n            for(int c=0;c<26;c++) {\n                if (!((mask>>c)&1)) {\n                    S[i]=c+\'a\';\n                    break;\n                }\n            }\n            if (S[i]==\'#\') return "";\n        }\n        \n        vector<vector<int>> estimated_lcp(n,vector<int>(n));\n        \n        for(int i=n-1;i>=0;i--) {\n            for(int j=n-1;j>=0;j--) {\n                if (S[i]!=S[j]) {\n                    estimated_lcp[i][j]=0;\n                } else {\n                    estimated_lcp[i][j]=1;\n                    if (i+1<n && j+1<n) estimated_lcp[i][j]+=estimated_lcp[i+1][j+1];\n                }\n            }\n        }\n        if (lcp != estimated_lcp) return "";\n        return S;\n    }\n};\n```
['C++']