Find the String with LCP

Find the String with LCP

1. What is this problem about?

The Find the String with LCP interview question is a reverse-engineering challenge. You are given an $n imes n$ matrix where lcp[i][j] is the length of the Longest Common Prefix (LCP) between the suffix of a string starting at index $i$ and the suffix starting at index $j$. Your task is to reconstruct the lexicographically smallest lowercase English string that matches this matrix. If no such string exists, return an empty string.

2. Why is this asked in interviews?

Google uses the Find the String with LCP coding problem to test a candidate's ability to handle consistency checks and relational data structures. It requires you to use Union Find or greedy logic to determine which indices must have the same character and then validate if the resulting string actually produces the given LCP matrix.

3. Algorithmic pattern used

This problem uses Greedy character assignment and Validation.

1. Grouping: If lcp[i][j] > 0, then s[i] must equal s[j]. Use a greedy pass to assign the smallest available characters ('a' to 'z') to indices, ensuring that connected indices get the same letter.
2. Lexicographical rule: Since we want the smallest string, try assigning 'a' first, then 'b', and so on.
3. Verification (Crucial): After building the candidate string, you MUST verify it. The LCP values must satisfy the recursive relationship: dp[i][j] = (s[i] == s[j]) ? dp[i+1][j+1] + 1 : 0.
4. If the calculated matrix matches the input matrix, return the string.

4. Example explanation

Matrix $2 imes 2$: [[2, 0], [0, 1]].

• lcp[0][1] = 0. So s[0] != s[1].
• Assign s[0] = 'a'.
• Assign s[1] = 'b'.
• Candidate: "ab".
• Verify: lcp("ab") -> lcp(0,0)=2, lcp(0,1)=0, lcp(1,1)=1. Matches! Result: "ab".

5. Common mistakes candidates make

• Skipping Validation: Simply building the string based on lcp[i][j] > 0 but failing to check if the exact LCP values (like 2, 3, etc.) are consistent.
• Alphabet limit: Not handling the case where more than 26 different characters are required.
• Complexity: Trying to validate the matrix in $O(N^3)$ instead of the $O(N^2)$ dynamic programming approach.

6. Interview preparation tip

Practice "Construction and Verification." This is a common Array interview pattern for hard problems. The key is to build the only possible candidate greedily and then spend $O(N^2)$ time ensuring every single constraint in the input is satisfied.