JS Solution - No Union Find, just edge cases checking
LOL getting accepted from this "edgy" problem right in the first try \uD83E\uDEE0\n\n# Approach\n## Part 1: Construct the string from a valid LCP\n- Assuming th
LOL getting accepted from this "edgy" problem right in the first try \uD83E\uDEE0\n\n# Approach\n## Part 1: Construct the string from a valid LCP\n- Assuming the given LCP **is already valid**, the problem is surprisingly easy, as `word[i] == word[j] if and only if lcp[i][j] > 0` (`Cond#0`). Btw that\'s why they would ask you to validate it as well so this is worth hard difficulty LOL.\n- To make `word` alphabetically smallest, we only have to prioritized the smallest unused character.\n- Pseudo-code:\n```\nlet chars = [undefined] * n;\nlet firstUnusedChar = "a";\n\nfor (i from 0 to n-1)\n    if (res[i] == undefined)\n        for (let j from i+1 to n-1)\n            if (lcp[i][j] > 0) res[i] = firstUnusedChar\n        firstUnusedChar = nextChar(firstUnusedChar)\n```\n\n## Part 2: Validating the LCP\nIDK if I\'ve overchecked any conditions but these are the ones that I came up with:\n- **`Cond#1`**: `lcp[i][i] == n - i` for each `0 <= i < n`;\n- **`Cond#2`**: `lcp[i][j] == lcp[j][i]` for each `0 <= i < n; 0 <= j < n`;\n- **`Cond#3`**: `lcp[i][j] < n - max(i, j)` for each `0 <= i < n; 0 <= j < n`;\n- **`Cond#4`**: either `lcp[i-1][j-1] == lcp[i][j] + 1` or `lcp[i-1][j-1] == 0` for each `0 < i < n; 0 < j < n`;\n- **`Cond#5`**: if `lcp[i][j] > 0` and `lcp[j][k] > 0`, then `lcp[i][i] > 0` `0 <= i < n; 0 <= j < n; 0 <= k < n;`;\n- **`Cond#6`**: The number of used character does not exceed `26`;\n\n**`Cond#5`** is the only tricky condition as it looks like it would take $$O(n^3)$$ to check. However, we can take advantage of the `chars` array. If **`Cond#0`** holds true, **`Cond#05`** is just equivalent to `if char[i] == char[j] && char[j] == char[k]; then char[i] == char[k]`, which is obviously true. In other words, **`Cond#5`** is just a derived statement from **`Cond#0`**, which takes only $$O(n^2)$$ to check.\nAll of the condition checking are noted in the code below. They may look different as I apply different tricks to optimize the code, but it is the same core logic that I\'ve shown.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```js\n/**\n * @param {number[][]} lcp\n * @return {string}\n */\nvar findTheString = function (lcp) {\n  let n = lcp.length;\n\n  for (let i = 0; i < n; i++) {\n    let bound = n - i;\n    // Cond#1\n    if (lcp[i][i] != bound) return "";\n\n    for (let j = 0; j < i; j++) {\n      // Cond#2  \n      if (lcp[i][j] != lcp[j][i]) return "";\n      // Cond#3\n      if (lcp[i][j] > bound) return "";\n      // Cond#4\n      if (lcp[i - 1][j - 1] && lcp[i][j] + 1 != lcp[i - 1][j - 1]) return "";\n    }\n  }\n\n  let chars = Array(n).fill();\n  let cc = 97;\n  let ch = "a";\n\n  for (let i = 0; i < n; i++) {\n    if (chars[i]) {\n      for (let j = 0; j < i; j++) {\n        // Cond#0\n        if ((chars[j] == chars[i]) ^ (lcp[i][j] > 0)) return "";\n      }\n      continue;\n    }\n    // Cond#6\n    if (cc > 122) return "";\n\n    // Cond#0\n    for (let j = 0; j < i; j++) {\n      if (lcp[i][j] > 0) return "";\n    }\n\n    ch = String.fromCharCode(cc++);\n    chars[i] = ch;\n\n    for (let j = i + 1; j < n; j++) {\n      if (lcp[i][j] > 0) {\n        // Cond#0\n        if (chars[j]) return "";\n        else chars[j] = ch;\n      }\n    }\n  }\n\n  return chars.join("");\n};\n```
['Greedy', 'JavaScript']