Java Solution With Explanation
First, construct a potential answer. The first character would always be \u2018a\u2019. Next we find the other characters by iterating from 1 to n - 1\n\nIn eac
First, construct a potential answer. The first character would always be \u2018a\u2019. Next we find the other characters by iterating from 1 to n - 1\n\nIn each iteration, we check values j from 0 to i - 1. If lcp[I][j] is greater than 0, it implies that i and j are same character so we can terminate the inner loop. If we don\u2019t find any j such that lcp[I][j] is greater than 0, we can set the ith character to the next unvisited character as this satisfies the lexicographical minimum constraints. Obviously if this character is greater than \u2018z\u2019, then we would return an empty string since we would need more than 26 characters to form such lcp array.\n\nOnce we have gotten a potential string that could serve as the answer, the next step would be validating if the entire lcp is correct. We can do this by constructing our own lcp from the potential string.\n\nWe can construct this using dynamic programming iterating backwards. If ith and jth character are different, then dp[i][j] is 0. Otherwise dp[I][j] is 1 + dp[i + 1][j + 1].  \n\nTime and Space complexity is O(n^2)\n\n\nPlease upvote if you like the solution :)\n\n```\nclass Solution {\n    public String findTheString(int[][] lcp) {\n        int n = lcp.length;\n        \n        // potential answer\n        char [] arr = new char [n];\n        arr[0] = \'a\';\n        \n        char test;\n        boolean found;\n        \n        for (int i = 1; i < n; ++i) {\n            test = \'a\';\n            found = false;\n            \n            for (int j = 0; j < i; ++j){\n                test = (char)Math.max(test, arr[j]);\n                \n                if (lcp[i][j] != 0){\n                    found = true;\n                    arr[i] = arr[j];  \n                    break;\n                }    \n            }\n            \n            if (found)\n                continue;\n            \n            ++test;\n            arr[i] = test;\n            \n            \n            // More than 26 characters needed. \n            if (test > \'z\')\n                return "";\n        }\n        \n        // lcp from potential string\n        int [][] dp = new int [n + 1][n + 1];\n        \n        int val;\n        \n        for (int i = n - 1; i >= 0; --i){\n            for (int j = n - 1; j >= 0; --j) {\n                if (arr[i] != arr[j])\n                    val = 0;\n                else\n                    val = 1 + dp[i + 1][j + 1];\n                \n                dp[i][j] = val;\n            }\n        }\n        \n        // compare dp and lcp as both should be same\n        for (int i = n - 1; i >= 0; --i){\n            for (int j = n - 1; j >= 0; --j) {\n                if (dp[i][j] != lcp[i][j])\n                    return "";\n            }\n        }\n        \n        return String.valueOf(arr);\n    }\n}\n```
['Dynamic Programming', 'Java']