#2573

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find the String with LCP

Determine the lexicographically smallest string matching a given LCP matrix using state transition dynamic programming.

array string dynamic programming greedy union find

Problem Statement

Given an n x n integer matrix lcp representing the longest common prefix lengths of a string word with itself, reconstruct the lexicographically smallest string word of length n consisting of lowercase English letters. Each lcp[i][j] equals the length of the longest common prefix of word[i...] and word[j...].

Return the alphabetically smallest string that matches the provided LCP matrix. If no such string exists due to inconsistent LCP values, return an empty string. Lexicographical order is determined by the first differing character; for example, "aabd" is smaller than "aaca".

Examples

Example 1

Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]

Output: "abab"

lcp corresponds to any 4 letter string with two alternating letters. The lexicographically smallest of them is "abab".

Example 2

Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]

Output: "aaaa"

lcp corresponds to any 4 letter string with a single distinct letter. The lexicographically smallest of them is "aaaa".

Example 3

Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]

Output: ""

lcp[3][3] cannot be equal to 3 since word[3,...,3] consists of only a single letter; Thus, no answer exists.

Constraints

1 <= n == lcp.length == lcp[i].length <= 1000
0 <= lcp[i][j] <= n

Solution Approach

Initialize characters and validate LCP constraints

Start by assigning each position a character placeholder and immediately check that the LCP matrix satisfies basic consistency rules, such as lcp[i][i] equal to the remaining substring length and symmetry for lcp[i][j] and lcp[j][i]. Any violation at this stage indicates no valid string exists.

Use state transition dynamic programming to propagate character equivalences

Iterate over the matrix and for each lcp[i][j] > 0, enforce that word[i] == word[j] and continue this equality for the next lcp[i][j]-1 characters. Track equivalence classes to handle multiple overlapping constraints efficiently. Resolve conflicts by marking impossible states to detect invalid configurations early.

Assign lexicographically smallest letters and construct the string

Once equivalence classes are established, assign the smallest available letter to each class in order. This guarantees lexicographical minimality. Finally, assemble the string from these assignments. If any LCP rule is violated during assignment, return an empty string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to checking all pairs in the LCP matrix and propagating equivalences. Space complexity is O(n) to store equivalence classes and the resulting string, though the LCP matrix itself requires O(n^2) storage.

What Interviewers Usually Probe

Candidate identifies matrix symmetry and self-prefix conditions.
Candidate uses dynamic programming to propagate equality constraints efficiently.
Candidate correctly detects impossible LCP configurations and returns empty string.

Common Pitfalls or Variants

Common pitfalls

Ignoring symmetry and failing to check lcp[i][j] == lcp[j][i].
Assigning letters before resolving all equivalence classes, which may violate LCP rules.
Misinterpreting lexicographical ordering when multiple choices of letters exist.

Follow-up variants

Find the largest lexicographical string matching an LCP matrix.
Handle LCP matrices with wildcard entries represented by -1.
Extend the problem to uppercase letters or a custom alphabet.

FAQ

What is the best approach for solving Find the String with LCP?

Using state transition dynamic programming to propagate character equivalences ensures all LCP constraints are satisfied.

How do I detect if no string can satisfy a given LCP matrix?

Check for violations such as lcp[i][j] != lcp[j][i] or inconsistent prefix lengths during propagation; any conflict indicates impossibility.

Can this problem be solved greedily instead of dynamic programming?

A purely greedy approach may fail due to overlapping equality constraints; DP ensures correct propagation across the matrix.

Why is lexicographical order important in this problem?

After equivalence classes are determined, assigning the smallest available letters guarantees the string is alphabetically minimal.

What patterns does Find the String with LCP primarily test?

It tests state transition dynamic programming with array and string constraints, focusing on prefix equality propagation and conflict detection.

terminal

Solution

Solution 1: Greedy + Construction

Since the constructed string requires the lexicographically smallest order, we can start by filling the string $s$ with the character `'a'`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        n = len(lcp)
        s = [""] * n
        i = 0
        for c in ascii_lowercase:
            while i < n and s[i]:
                i += 1
            if i == n:
                break
            for j in range(i, n):
                if lcp[i][j]:
                    s[j] = c
        if "" in s:
            return ""
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if s[i] == s[j]:
                    if i == n - 1 or j == n - 1:
                        if lcp[i][j] != 1:
                            return ""
                    elif lcp[i][j] != lcp[i + 1][j + 1] + 1:
                        return ""
                elif lcp[i][j]:
                    return ""
        return "".join(s)

Continue Practicing

#2617 minimum number of visited cells in a grid #1578 minimum time to make rope colorful #2556 disconnect path in a binary matrix by at most one flip