Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A positive LCP entry forces the two suffixes' first characters to match; a zero entry requires them to differ. Assigning the smallest unused letter to the earliest unassigned position gives the lexicographically smallest candidate. However, matching first characters alone does not guarantee the full LCP lengths, so the entire matrix must be validated afterward.

Approach

Scan positions in order. For each unassigned one, assign the next letter to all later positions with positive LCP against it, rejecting if more than 26 groups are required. Then check every matrix cell: unequal assigned letters require zero; equal letters require one plus the diagonally following LCP value, or one at a boundary. Return an empty string on any mismatch. If every recurrence holds, assemble and return the candidate.

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        n = len(lcp)
        curr = 1
        letters = [0] * n

        for i in range(n):
            if letters[i]: continue
            if curr > 26: return ''
            for j in range(i, n):
                if lcp[i][j]: letters[j] = curr
            curr += 1
        
        for i in range(n):
            for j in range(n):
                if letters[i] != letters[j]: expected = 0
                else: expected = (lcp[i + 1][j + 1] if i < n - 1 and j < n - 1 else 0) + 1
                if expected != lcp[i][j]: return ''
        
        res = ''

        for num in letters: res += chr(ord('a') - 1 + num)

        return res

Complexity analysis

Let n = lcp.length. Greedy letter assignment followed by full matrix validation takes O(n^2) time. Auxiliary space is O(n) for assigned letters and the candidate string.