Find the String with LCP

Hard
1266.

Find the String with LCP

Find the String with LCP is a hard coding problem on strings, dynamic programming and greedy, asked in Amazon and Google interviews.

For a string word of length n made of lowercase letters, its LCP matrix is the n × n grid where lcp[i][j] is the length of the longest common prefix of the suffixes word[i..n-1] and word[j..n-1].

Given an n × n matrix lcp, return the lexicographically smallest string word whose LCP matrix is exactly lcp. If no such string exists, return an empty string.

Example 1

Input
lcp = [[3,1,0],[1,2,0],[0,0,1]]
Output
"aab"
Explanation
Positions 0 and 1 share a letter, position 2 differs; `aab` is the smallest such string and its matrix matches.

Example 2

Input
lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
Output
"aaaa"

Example 3

Input
lcp = [[3,1,0],[1,2,0],[0,0,2]]
Output
""
Explanation
`lcp[2][2]` must be 1 — the suffix starting at index 2 has length 1.

Constraints

  • 1 <= n == lcp.length == lcp[i].length <= 1000
  • 0 <= lcp[i][j] <= n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} lcp
 * @return {string}
 */
var findTheString = function(lcp) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the String with LCP — Solution in Python, Java & C++

Find the String with LCP solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Find the String with LCP is a hard coding problem on strings, dynamic programming and greedy, asked in Amazon and Google interviews.

Problem statement

For a string word of length n made of lowercase letters, its LCP matrix is the n × n grid where lcp[i][j] is the length of the longest common prefix of the suffixes word[i..n-1] and word[j..n-1].

Given an n × n matrix lcp, return the lexicographically smallest string word whose LCP matrix is exactly lcp. If no such string exists, return an empty string.

Example 1

Input: lcp = [[3,1,0],[1,2,0],[0,0,1]]
Output: "aab"
Explanation: Positions 0 and 1 share a letter, position 2 differs; `aab` is the smallest such string and its matrix matches.

Example 2

Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
Output: "aaaa"

Example 3

Input: lcp = [[3,1,0],[1,2,0],[0,0,2]]
Output: ""
Explanation: `lcp[2][2]` must be 1 — the suffix starting at index 2 has length 1.

Constraints

  • 1 <= n == lcp.length == lcp[i].length <= 1000
  • 0 <= lcp[i][j] <= n

Hints for Find the String with LCP

  1. Hint 1

    lcp[i][j] > 0 says exactly that word[i] == word[j]. So the matrix fixes which positions share a letter.

  2. Hint 2

    For the smallest string, give position 0 the letter a, copy it to every j with lcp[0][j] > 0, then give the next unlabelled position b, and so on. More than 26 groups means no answer.

  3. Hint 3

    The labelling is only a candidate — rebuild its LCP matrix with L[i][j] = (word[i] == word[j]) ? L[i+1][j+1] + 1 : 0 from the bottom-right corner and compare every entry with the input.

How to solve Find the String with LCP

The positivity pattern of lcp determines which positions hold equal letters, and the lexicographically smallest string with a given equality pattern introduces new letters in order of first appearance. Build that candidate greedily, then verify the whole matrix with the standard LCP recurrence.

Approach

  1. Walk i from 0 to n - 1. If word[i] is unassigned, assign it the next unused letter (fail if all 26 are used) and assign the same letter to every unassigned j > i with lcp[i][j] > 0.
  2. Verify: for i and j from n - 1 down to 0, compute L = (word[i] == word[j]) ? L[i+1][j+1] + 1 : 0 (with L[n][*] = L[*][n] = 0); if any L != lcp[i][j], return the empty string. Two rolling rows suffice.
  3. Return the assigned letters as a string.

Why it works

Any valid string satisfies word[i] == word[j] ⇔ lcp[i][j] > 0, so all valid strings share one partition of the positions; among them, the lexicographically smallest labels the groups a, b, c, … in order of their first position, which is what the greedy pass does. If the input is valid, that candidate's matrix equals the input; if the candidate's matrix differs, no string can match. The recurrence is exactly how LCPs of suffixes extend, so the verification is complete.

Complexity

  • Time — O(n^2)
  • Space — O(n) besides the input

Pitfalls

  • Skipping verification — the matrix may be inconsistent (asymmetric, wrong diagonal, wrong lengths) even when the greedy pass succeeds.
  • Needing a 27th letter means there is no answer.
  • Checking only lcp[i][j] > 0 is not enough; the exact values must match the recurrence.

Reference solution

Python

from typing import List

def findTheString(lcp: List[List[int]]) -> str:
    n = len(lcp)
    word = [-1] * n
    c = 0
    for i in range(n):
        if word[i] != -1:
            continue
        if c == 26:
            return ""
        word[i] = c
        for j in range(i + 1, n):
            if word[j] == -1 and lcp[i][j] > 0:
                word[j] = c
        c += 1
    nxt = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        cur = [0] * (n + 1)
        row = lcp[i]
        for j in range(n - 1, -1, -1):
            v = nxt[j + 1] + 1 if word[i] == word[j] else 0
            if v != row[j]:
                return ""
            cur[j] = v
        nxt = cur
    return "".join(chr(97 + x) for x in word)

Java

public static String findTheString(int[][] lcp) {
    int n = lcp.length;
    int[] word = new int[n];
    Arrays.fill(word, -1);
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (word[i] != -1) continue;
        if (c == 26) return "";
        word[i] = c;
        for (int j = i + 1; j < n; j++) if (word[j] == -1 && lcp[i][j] > 0) word[j] = c;
        c++;
    }
    int[] nxt = new int[n + 1], cur = new int[n + 1];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int v = word[i] == word[j] ? nxt[j + 1] + 1 : 0;
            if (v != lcp[i][j]) return "";
            cur[j] = v;
        }
        int[] t = nxt;
        nxt = cur;
        cur = t;
    }
    StringBuilder sb = new StringBuilder();
    for (int x : word) sb.append((char) ('a' + x));
    return sb.toString();
}

C++

string findTheString(vector<vector<int>>& lcp) {
    int n = lcp.size();
    vector<int> word(n, -1);
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (word[i] != -1) continue;
        if (c == 26) return "";
        word[i] = c;
        for (int j = i + 1; j < n; j++) if (word[j] == -1 && lcp[i][j] > 0) word[j] = c;
        c++;
    }
    vector<int> nxt(n + 1, 0), cur(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int v = word[i] == word[j] ? nxt[j + 1] + 1 : 0;
            if (v != lcp[i][j]) return "";
            cur[j] = v;
        }
        swap(nxt, cur);
    }
    string res;
    for (int x : word) res += (char)('a' + x);
    return res;
}

JavaScript

var findTheString = function(lcp) {
    var n = lcp.length;
    var word = new Array(n).fill(-1);
    var c = 0;
    for (var i = 0; i < n; i++) {
        if (word[i] !== -1) continue;
        if (c === 26) return "";
        word[i] = c;
        for (var j = i + 1; j < n; j++) if (word[j] === -1 && lcp[i][j] > 0) word[j] = c;
        c++;
    }
    var nxt = new Array(n + 1).fill(0);
    for (var i2 = n - 1; i2 >= 0; i2--) {
        var cur = new Array(n + 1).fill(0);
        for (var j2 = n - 1; j2 >= 0; j2--) {
            var v = word[i2] === word[j2] ? nxt[j2 + 1] + 1 : 0;
            if (v !== lcp[i2][j2]) return "";
            cur[j2] = v;
        }
        nxt = cur;
    }
    var res = "";
    for (var k = 0; k < n; k++) res += String.fromCharCode(97 + word[k]);
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming