Description
We define the lcp matrix of any 0-indexed string word of n lowercase English letters as an n x n grid such that:
lcp[i][j]is equal to the length of the longest common prefix between the substringsword[i,n-1]andword[j,n-1].
Given an n x n matrix lcp, return the alphabetically smallest string word that corresponds to lcp. If there is no such string, return an empty string.
A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "aabd" is lexicographically smaller than "aaca" because the first position they differ is at the third letter, and 'b' comes before 'c'.
Example 1:
Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]] Output: "abab" Explanation: lcp corresponds to any 4 letter string with two alternating letters. The lexicographically smallest of them is "abab".
Example 2:
Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]] Output: "aaaa" Explanation: lcp corresponds to any 4 letter string with a single distinct letter. The lexicographically smallest of them is "aaaa".
Example 3:
Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]] Output: "" Explanation: lcp[3][3] cannot be equal to 3 since word[3,...,3] consists of only a single letter; Thus, no answer exists.
Constraints:
1 <= n ==lcp.length ==lcp[i].length<= 10000 <= lcp[i][j] <= n
Solutions
The code constructs a string that matches a given longest common prefix (LCP) matrix. It starts by assigning characters sequentially from 'a' onwards to each unassigned position in the word, and propagates the same character to any subsequent positions that should match (based on lcp values). Then it validates the constructed word against the LCP matrix through a backwards scan: if two positions have different characters, their lcp[i][j] must be 0; if either position is at the end, lcp[i][j] must be 1 (matching only the character itself); otherwise, lcp[i][j] must equal lcp[i+1][j+1] + 1 (their common prefix extends one position beyond the next positions' match). If the word uses more than 26 letters (running out of the alphabet) or any constraint fails, it returns an empty string; otherwise, it returns the constructed word joined together.
/**
* @param {number[][]} lcp
* @return {string}
*/
var findTheString = function (lcp) {
const n = lcp.length;
const aChar = "a".charCodeAt(0);
const zChar = "z".charCodeAt(0);
const word = new Array(n).fill("");
let current = aChar;
for (let i = 0; i < n; i++) {
if (word[i]) {
continue;
}
if (current > zChar) {
return "";
}
word[i] = String.fromCharCode(current);
for (let j = i + 1; j < n; j++) {
if (lcp[i][j] > 0) {
word[j] = word[i];
}
}
current++;
}
for (let i = n - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
if (word[i] !== word[j]) {
if (lcp[i][j] !== 0) {
return "";
}
continue;
}
if (i === n - 1 || j === n - 1) {
if (lcp[i][j] !== 1) {
return "";
}
continue;
}
if (lcp[i][j] !== lcp[i + 1][j + 1] + 1) {
return "";
}
}
}
return word.join("");
};