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.
This approach involves constructing the string one character at a time, ensuring that it is the lexicographically smallest string that corresponds to the given LCP matrix. We'll employ a greedy method where we fill the string position by position, always choosing the smallest valid letter that satisfies the LCP constraints.
This Python solution creates the word by systematically filling in each character position with the alphabetically smallest character satisfying the LCP constraints. Starting with 'a' for the first unassigned position, it checks and assigns subsequent characters while ensuring consistent overlap with previously assigned sections. If inconsistencies are detected based on the LCP metrics, it immediately returns an empty string.
Time Complexity: O(n^2 * Alphabet Size), as it constructs pairs for each position.
Space Complexity: O(n), for the resulting word array.
This approach involves using dynamic programming to verify and construct the string iteratively. It checks and confirms LCP-derived constraints in a systematic manner, ensuring there are no contradictions in the substring relationships.
This Java solution employs a dynamic programming mindset to determine character assignments based on the LCP matrix. It uses an initial array filled with default (null or empty) values and iteratively assigns the lexicographically smallest character while verifying all provided constraints. If any inconsistency is discovered, an immediate empty string return occurs.
Java
JavaScript
Time Complexity: O(n^3), because of the triple nested loop structure involved in validation.
Space Complexity: O(n), due to the character array storage.
Since the constructed string requires the lexicographically smallest order, we can start by filling the string s with the character 'a'.
If the current position i has not been filled with a character, then we can fill the character 'a' at position i. Then we enumerate all positions j > i. If lcp[i][j] > 0, then position j should also be filled with the character 'a'. Then we add one to the ASCII code of the character 'a' and continue to fill the remaining unfilled positions.
After filling, if there are unfilled positions in the string, it means that the corresponding string cannot be constructed, so we return an empty string.
Next, we can enumerate each position i and j in the string from large to small, and then judge whether s[i] and s[j] are equal:
s[i] = s[j], at this time we need to judge whether i and j are the last positions of the string. If so, then lcp[i][j] should be equal to 1, otherwise lcp[i][j] should be equal to 0. If the above conditions are not met, it means that the corresponding string cannot be constructed, so we return an empty string. If i and j are not the last positions of the string, then lcp[i][j] should be equal to lcp[i + 1][j + 1] + 1, otherwise it means that the corresponding string cannot be constructed, so we return an empty string.lcp[i][j] > 0, it means that the corresponding string cannot be constructed, so we return an empty string.If every position in the string meets the above conditions, then we can construct the corresponding string and return it.
The time complexity is O(n^2), and the space complexity is O(n). Where n is the length of the string.
| Approach | Complexity |
|---|---|
| Greedy Lexicographical Construction | Time Complexity: O(n^2 * Alphabet Size), as it constructs pairs for each position. |
| Dynamic Programming with Constraints Verification | Time Complexity: O(n^3), because of the triple nested loop structure involved in validation. |
| Greedy + Construction | — |
| 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 |
Find the String with LCP | Deep Dive | Dry Runs | 2 Ways | Leetcode 2573 | codestorywithMIK • codestorywithMIK • 8,226 views views
Watch 9 more video solutions →Practice Find the String with LCP with our built-in code editor and test cases.
Practice on FleetCode