Skip to main content
Talentd

Find the String with LCP - Solution & Explanation

HardArrayStringDynamic ProgrammingGreedy20 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 1000
  • 0 <= lcp[i][j] <= n

Approach Overview

Problem 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 1: Greedy Lexicographical Construction

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n^2 * Alphabet Size), as it constructs pairs for each position.
Space Complexity: O(n), for the resulting word array.

Try this approach in the editor →

Approach 2: Dynamic Programming with Constraints Verification

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Greedy + Construction

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:

  • If 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.
  • Otherwise, if 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Lexicographical Construction

Time Complexity: O(n^2 * Alphabet Size), as it constructs pairs for each position.
Space Complexity: O(n), for the resulting word array.

Dynamic Programming with Constraints Verification

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.

Greedy + Construction—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Union-Find Character GroupingO(n^2)O(n)When equality constraints dominate and you want to group indices efficiently
Greedy Lexicographical ConstructionO(n^2)O(n)Best practical approach for constructing a minimal valid string
Dynamic Programming VerificationO(n^2)O(n^2)When you want explicit validation that the generated string matches the LCP matrix

Video Solution

Find the String with LCP | Deep Dive | Dry Runs | 2 Ways | Leetcode 2573 | codestorywithMIK • codestorywithMIK • 9,070 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the String with LCP easy or hard?
Find the String with LCP is classified as a Hard problem. The challenge comes from interpreting the matrix as a set of prefix constraints and constructing a string that satisfies both direct character equality and deeper suffix relationships.
Find the String with LCP Python/Java solution
Python and C++ implementations usually follow the greedy construction approach with validation. Java and JavaScript solutions often compute an additional DP table to verify LCP relationships. All implementations typically run in O(n^2) time since the matrix must be processed.
How to solve Find the String with LCP in O(n^2)?
Interpret the matrix as constraints between indices. If lcp[i][j] > 0, characters at those indices must match. Build the string greedily or with Union-Find grouping, then validate by recomputing LCP values using a DP recurrence: dp[i][j] = 1 + dp[i+1][j+1] when characters match. This ensures the constructed string exactly reproduces the matrix.
What is the best approach for Find the String with LCP?
The most practical approach is greedy lexicographical construction combined with verification. Assign the smallest possible characters while respecting equality constraints derived from the LCP matrix. After building the string, recompute the LCP table to ensure it matches the given matrix. This runs in O(n^2) time and O(n) space.
Is Find the String with LCP asked at Google/Amazon/Meta?
Matrix constraint reconstruction and suffix prefix relationships appear frequently in interviews at large tech companies. Variants involving string reconstruction, union-find constraints, and suffix comparisons have been reported in interviews at companies like Google and Amazon.
What data structure is used in Find the String with LCP?
Common solutions use Union-Find to group indices that must share the same character. Dynamic programming is used to verify longest common prefix relationships, while arrays and matrices store constraints derived from the input.
What is the time complexity of Find the String with LCP?
Most optimal implementations run in O(n^2) time because the input itself is an n x n matrix. Constructing the string and validating LCP relationships both require iterating over matrix entries. Space complexity ranges from O(n) for greedy construction to O(n^2) if a DP verification table is used.

Ready to solve this problem?

Practice Find the String with LCP with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays