Had my phone screen today. Implemented the below question with O(n^2)complexity. Interview was wrapped up with 15 mins reamaining.

You're building a text deduplication service for Google Docs. To optimize storage and reduce repeated content, your team precomputes the longest common prefix (LCP) between suffixes of document content. This LCP matrix helps the backend efficiently identify and compress repeating text patterns.

During a debugging session, your teammate accidentally deleted the original string but left behind a previously computed LCP matrix. To test your compression algorithm, you now need to reconstruct the lexicographically smallest string that could have produced this LCP matrix.

Given a 2D LCP matrix for a string of length n, reconstruct the lexicographically smallest valid string that corresponds to this LCP matrix. If no such string exists, return an empty string.
Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
Output: "abab"

Edit - this question is already present on leetcode https://leetcode.com/problems/find-the-string-with-lcp/description/?envType=problem-list-v2&envId=matrix