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.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Greedy, Matrix
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 10000 <= lcp[i][j] <= n
Hints for Find the String with LCP
Hint 1
lcp[i][j] > 0says exactly thatword[i] == word[j]. So the matrix fixes which positions share a letter.Hint 2
For the smallest string, give position 0 the letter
a, copy it to everyjwithlcp[0][j] > 0, then give the next unlabelled positionb, and so on. More than 26 groups means no answer.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 : 0from 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
- Walk
ifrom 0 ton - 1. Ifword[i]is unassigned, assign it the next unused letter (fail if all 26 are used) and assign the same letter to every unassignedj > iwithlcp[i][j] > 0. - Verify: for
iandjfromn - 1down to 0, computeL = (word[i] == word[j]) ? L[i+1][j+1] + 1 : 0(withL[n][*] = L[*][n] = 0); if anyL != lcp[i][j], return the empty string. Two rolling rows suffice. - 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] > 0is 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