Problem Statement in English

You’re given a 2D array lcp of size n x n where lcp[i][j] is the length of the longest common prefix of the suffixes of a string s starting at indices i and j.

Your task is to find the lexicographically smallest string s of length n that corresponds to the given lcp array. If there is no such string, return an empty string.

Approach

There are two main steps to solve this problem:

  • Construction of the string
  • Validation of the constructed string against the lcp array - because the input matrix could be invalid (in which case we should return an empty string)

Let’s start with the construction of the string.

We can iterate through the lcp array and whenever we encounter a non-zero value at lcp[i][j], it means that the characters at indices i and j in the string must be the same. Thus, we can use a greedy approach to assign the current character to the string at index i and all indices j where lcp[i][j] is non-zero. We can keep track of the next available character using a variable current, which starts at ‘a’ and increments whenever we assign a new character.

Now for the verification step, we need to ensure that the constructed string satisfies the conditions given by the lcp array, and that the lcp array is actually legitimate.

A couple checks we can perform are:

  • if lcp[i][j] is non-zero, then lcp[j][i] should also be non-zero, and the characters at indices i and j should be the same.
  • if i or j is the last index, then lcp[i][j] should be 1 if the characters are the same, and 0 otherwise.
  • for other indices, lcp[i][j] should be one more than lcp[i + 1][j + 1] (the next character) if the characters at indices i and j are the same, and should be 0 if they are different.

And we are done!

Solution in Python


class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        n = len(lcp)
        word = [""] * n
        current = ord("a")

        for i in range(n):
            if not word[i]:
                if current > ord("z"):
                    return ""
                word[i] = chr(current)
                for j in range(i + 1, n):
                    if lcp[i][j]:
                        word[j] = word[i]
                current += 1

        for i in reversed(range(n)):
            for j in reversed(range(n)):
                if word[i] != word[j]:
                    if lcp[i][j]:
                        return ""
                else:
                    if i == n - 1 or j == n - 1:
                        if lcp[i][j] != 1:
                            return ""
                    else:
                        if lcp[i][j] != lcp[i + 1][j + 1] + 1:
                            return ""

        return "".join(word)

Complexity

  • Time: $O(n^2)$
    Since we have a nested loop to construct the string and another nested loop to validate it.

  • Space: $O(n)$
    Since we store the constructed string in an array of size n.

Mistakes I Made

I had to look this one up :(

And we are done.