Collect requirements, then build greedily to satisfy it
Intuition\n/\nLCP Must be;\n1) symmetric matrix\n2) diagonal element is [n,n-1,n-2,...,1]\n3) less then equal at least.\n  {4, 3, 2, 1},\n  {3, 3, 2, 1},\n  {2,
# Intuition\n/*\nLCP Must be;\n1) symmetric matrix\n2) diagonal element is [n,n-1,n-2,...,1]\n3) less then equal at least.\n  {4, 3, 2, 1},\n  {3, 3, 2, 1},\n  {2, 2, 2, 1},\n  {1, 1, 1, 1};\n\n*/\n\nWe just try to create `word` greedily,\nthen verify the `word` is surely the proper answer.\n\n\n# Approach\n\n/*\nBrute force.\n\n- Assert requirements.\n- Build matrix greedily.\n- Reconstruct LCP from the word built and validate the given LCP is created.\n*/\n\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n- Space complexity:\nO(n^2)\n\n```\nclass Solution {\n  public String findTheString(int[][] lcp) {\n    int n = lcp.length;\n    if (!isDiag(lcp, n)) { // Assert matrix is diagonal\n      return "";\n    }\n    if (!isLeq(lcp, n)) { // Assert value is less than possible max value at each cell.\n      return "";\n    }\n\n    var w = new char[n];\n    { // Build matrix greedily to create the smallest word.\n      // As matrix is symmetric, building lower triangular matrix is enough.\n      w[0] = \'a\';\n      for (int c = 0; c < n; c++) {\n        for (int r = c; r < n; r++) {\n          if (lcp[r][c] == 0) {\n            if (w[r] == w[c] || w[r] == \'\\0\') {\n              w[r] = (char) (w[c] + 1);\n            }\n          } else {\n            w[r] = w[c];\n          }\n        }\n      }\n    }\n    // Check only alphabetic char is used.\n    for (int i = 0; i < w.length; i++) {\n      if (!Character.isAlphabetic(w[i])) {\n        return "";\n      }\n    }\n\n    var s = String.valueOf(w);\n    // Reconstruct LCP from the word built and validate the given LCP is created.\n    if (!Arrays.deepEquals(buildLcp(w, n), lcp)) { // validate\n      return "";\n    }\n    return s;\n  }\n\n  private int[][] buildLcp(char[] s, int n) {\n    var res = new int[n][n];\n    for (int r = n - 1; r >= 0; r--) {\n      for (int c = n - 1; c >= 0; c--) {\n        if (s[r] == s[c]) {\n          res[r][c] = 1;\n          if (r + 1 < n && c + 1 < n) {\n            res[r][c] += res[r + 1][c + 1];\n          }\n        }\n      }\n    }\n    return res;\n  }\n\n  private boolean isLeq(int[][] lcp, int n) {\n    for (int r = 0; r < n; r++) {\n      int remRow = n - r;\n      for (int c = 0; c < n; c++) {\n        int remCol = n - c;\n        var v = lcp[r][c];\n        if (v > remRow || v > remCol) {\n          return false;\n        }\n        if (r == c && v != remRow) {\n          return false;\n        }\n      }\n    }\n    return true;\n  }\n\n  private boolean isDiag(int[][] lcp, int n) {\n    for (int r = 0; r < n; r++) {\n      for (int c = r; c < n; c++) {\n        if (lcp[r][c] != lcp[c][r]) {\n          return false;\n        }\n      }\n    }\n    return true;\n  }\n}\n\n\n```
['Java']