Watch 10 video solutions for Find the String with LCP, a hard level problem involving Array, String, Dynamic Programming. This walkthrough by codestorywithMIK has 8,226 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 substrings word[i,n-1] and word[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] <= nProblem Overview: You are given an n x n matrix where lcp[i][j] represents the length of the longest common prefix between the suffixes of a string starting at indices i and j. The task is to reconstruct any valid string that produces this matrix, or return an empty string if the matrix is inconsistent.
Approach 1: Union-Find Character Grouping (O(n^2) time, O(n) space)
The matrix implies equality constraints between positions. If lcp[i][j] > 0, then s[i] must equal s[j]. A Union Find structure groups indices that must share the same character. Iterate through the matrix and union all pairs that require matching characters. After building components, assign the smallest possible characters ('a', 'b', 'c', ...) to each group. Finally, recompute the LCP values to verify they match the input matrix. This approach directly models the equality constraints and keeps the string lexicographically minimal.
Approach 2: Greedy Lexicographical Construction (O(n^2) time, O(n) space)
Build the string from left to right while respecting the LCP constraints. When lcp[i][j] > 0, the characters at i and j must match, and the suffix starting at i+1 and j+1 must share lcp[i][j] - 1 characters. Start by assigning the smallest unused character when encountering a new position, then propagate the same character to positions that require equality. This greedy approach ensures the constructed string remains lexicographically smallest while satisfying constraints derived from the matrix. After construction, recompute the LCP table to confirm correctness.
Approach 3: Dynamic Programming with Constraints Verification (O(n^2) time, O(n^2) space)
Another strategy constructs the string first and then verifies LCP values using dynamic programming. After assigning characters based on equality requirements, compute a DP table where dp[i][j] represents the longest common prefix of suffixes starting at i and j. The recurrence is straightforward: if s[i] == s[j], then dp[i][j] = 1 + dp[i+1][j+1], otherwise 0. Compare this computed table with the original matrix. The DP validation step ensures that both direct character equality and deeper suffix relationships are correct. This approach uses classic suffix comparison logic often seen in dynamic programming and string problems.
Recommended for interviews: The greedy lexicographical construction combined with constraint verification is typically expected. It demonstrates the ability to interpret matrix constraints, construct a valid string, and validate correctness. Mentioning the Union-Find perspective shows deeper understanding of equality constraints, while the DP verification step proves the result matches the LCP definition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find Character Grouping | O(n^2) | O(n) | When equality constraints dominate and you want to group indices efficiently |
| Greedy Lexicographical Construction | O(n^2) | O(n) | Best practical approach for constructing a minimal valid string |
| Dynamic Programming Verification | O(n^2) | O(n^2) | When you want explicit validation that the generated string matches the LCP matrix |