Easy greedy + DP | Video solution | Intuitive approach
Intuition\nIn order to form the smallest lexicographic string we always would be starting the result with \'a\'. any index $j>0$ (0 base indexing and index 0 ha
# Intuition\nIn order to form the smallest lexicographic string we always would be starting the result with \'a\'. any index $j>0$ (0 base indexing and index 0 has already been set to \'a\'), would be having the value at index $i$ $(i<j)$ if $lcp[i][j]>0$, else assign it the minimum unutilized character. \n\n\nVideo solution: https://youtu.be/BotxOAPrYnY\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. assign character \'a\' to the 0th index, let\'s call the string as res \n2. run loop for $i=1$ to size-1\n3. check for the leftmost index j $(j<i)$ such that $lcp[i][j]>0$ if such an index exist then assign $res[i]=res[j]$\n4. If such an index is not found then assign minimum unused character to $res[i]$\n5. In order to verify if the string is valid, construct a longest similar suffix dp array.\n6. If the dp array is exactly equal to the lcp then answer constructed is valid else return empty string (for invalid answer)\n# Complexity\n- Time complexity:\n $$O(n^2)$$ \n\n- Space complexity:\n $$O(n^2)$$ \n# Code\n```\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        int n=lcp.size();\n        string res(n,\'a\');\n        res[0]=\'a\';     \n        char mn=\'b\';\n        for(int i=1;i<n;i++)\n        {\n            bool set=false;\n            for(int j=0;j<i;j++){\n                if(lcp[i][j]!=0){\n                    set=true;\n                    res[i]=res[j];\n                    break;\n                }\n            }\n            if(!set)    res[i]=mn++;\n        }\n        for(int i=0;i<n;i++)    if(res[i]>\'z\')  return "";\n        vector<vector<int>> dp(n,vector<int>(n,0));     // suffix count\n\n        for(int i=n-1;i>=0;i--)\n            for(int j=n-1;j>=0;j--)\n                if(res[i]==res[j])  dp[i][j]=1+((i<n-1 && j<n-1)?dp[i+1][j+1]:0);\n        \n        for(int i=0;i<n;i++)        // now my 2 arrays should be equal\n            for(int j=0;j<n;j++)\n                if(dp[i][j]!=lcp[i][j]) return "";\n        \n        \n        return res;\n    }\n};\n```
['C++']