Word From a Prefix Table

Hard

For a word word of length n made of lowercase English letters, build an n × n table where cell [i][j] holds the length of the longest common prefix of the suffixes word[i:] and word[j:]. You are given such a table table. Recover the word from it: return the lexicographically smallest word whose table is exactly this one. If no word fits, return the empty string.

Example 1

table=[[3, 0, 1], [0, 2, 0], [1, 0, 1]] → 'aba'

The suffixes of "aba" are "aba", "ba" and "a": the first and third share a prefix of length 1, and "ba" shares no prefix with either. That is exactly the given table, and "aba" is the smallest word that fits.

Example 2

table=[[2, 1], [1, 1]] → 'aa'

The suffixes "aa" and "a" share a prefix of length 1.

Example 3

table=[[2, 0], [0, 2]] → ''

The diagonal holds the length of each suffix itself, and the last suffix is a single letter, so it cannot be 2. The answer is the empty string.

Constraints

1 ≤ n == len(table) == len(table[i]) ≤ 1000
0 ≤ table[i][j] ≤ n

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Union Find Array String Dynamic Programming Matrix

Similar problems

Long Leaps Across a Board Hard Bead String Without Twins Medium Alternating Team Picks Easy Does the Text Fit the Pattern Hard Biggest Solid Panel Block Hard

Input

table=[[3, 0, 1], [0, 2, 0], [1, 0, 1]]

Expected

'aba'

Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.