Find the String with LCP

HARD

Description

We define the lcp matrix of any 0-indexed string word of n lowercase English letters as an n x n grid such that:

lcp[i][j] is equal to the length of the longest common prefix between the substrings word[i,n-1] and word[j,n-1].

Given an n x n matrix lcp, return the alphabetically smallest string word that corresponds to lcp. If there is no such string, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "aabd" is lexicographically smaller than "aaca" because the first position they differ is at the third letter, and 'b' comes before 'c'.

Example 1:

Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
Output: "abab"
Explanation: 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"
Explanation: 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: ""
Explanation: 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

Approaches

Checkout 2 different approaches to solve Find the String with LCP. Click on different approaches to view the approach and algorithm in detail.

Backtracking Search

This approach involves building the string character by character from left to right. At each position, we try to place a character from 'a' to 'z'. After placing a character, we check if the prefix of the string built so far is consistent with the given lcp matrix. If it's not consistent, we backtrack and try the next character. If we successfully build a complete string of length n, we have found the lexicographically smallest solution because we explore characters in alphabetical order.

Algorithm

Define a recursive function, say solve(index, currentWord), that attempts to build the string character by character.
The base case is index == n. When reached, a full candidate string is formed. Validate this string against the lcp matrix. If it matches, a solution is found.
In the recursive step for index, iterate through characters c from 'a' to 'z'.
For each character c, assign currentWord[index] = c.
Perform a partial validation of the prefix currentWord[0...index] against the lcp matrix. Check for any immediate contradictions with lcp[i][j] for i, j <= index.
If the prefix is consistent, make a recursive call solve(index + 1, currentWord).
If the recursive call finds a solution, return it. Otherwise, backtrack and try the next character.
Since characters are tried in alphabetical order ('a' to 'z'), the first complete valid string found will be the lexicographically smallest.

The backtracking algorithm explores the search space of all possible strings of length n. It does so by constructing the string one character at a time. To ensure the result is lexicographically smallest, it tries placing 'a', then 'b', and so on, at each position.

After adding a character at index k, the algorithm checks if the prefix of length k+1 violates any conditions imposed by the lcp matrix. For example, if we have word[i] and word[j] (with i, j <= k), and word[i] != word[j], then lcp[i][j] must be 0. If the input lcp[i][j] is greater than 0, this path is invalid, and the algorithm must backtrack.

This pruning of invalid paths helps reduce the search space, but the worst-case complexity remains exponential. A full validation is required once a complete string is formed.

Due to its high time complexity, this approach is not practical for the given problem constraints but serves as a theoretical brute-force method.

Complexity Analysis

Time Complexity: O(26^n)Space Complexity: O(n)

Pros and Cons

Pros:

Conceptually straightforward as it's an exhaustive search.
Guaranteed to find the lexicographically smallest string if one exists.

Cons:

Extremely high time complexity, making it infeasible for the given constraints (n up to 1000).
The logic for partial validation at each step is complex to implement correctly and efficiently.

Code Solutions

Checking out 3 solutions in different languages for Find the String with LCP. Click on different languages to view the code.

class Solution {
public
  String findTheString(int[][] lcp) {
    int n = lcp.length;
    char[] s = new char[n];
    int i = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
      while (i < n && s[i] != '\0') {
        ++i;
      }
      if (i == n) {
        break;
      }
      for (int j = i; j < n; ++j) {
        if (lcp[i][j] > 0) {
          s[j] = c;
        }
      }
    }
    for (i = 0; i < n; ++i) {
      if (s[i] == '\0') {
        return "";
      }
    }
    for (i = n - 1; i >= 0; --i) {
      for (int j = n - 1; j >= 0; --j) {
        if (s[i] == s[j]) {
          if (i == n - 1 || j == n - 1) {
            if (lcp[i][j] != 1) {
              return "";
            }
          } else if (lcp[i][j] != lcp[i + 1][j + 1] + 1) {
            return "";
          }
        } else if (lcp[i][j] > 0) {
          return "";
        }
      }
    }
    return String.valueOf(s);
  }
}

Video Solution

Watch the video walkthrough for Find the String with LCP

Algorithms:

Union Find

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

ArrayStringMatrix