# Find the String with LCP
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-string-with-lcp)
Canonical: https://scaleengineer.com/dsa/problems/find-the-string-with-lcp
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, String, Matrix
---
## Problem
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
## 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.
**Time:** O(26^n) · **Space:** O(n)
**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.
### Explanation
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.
### 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.

## Greedy Construction with Verification
A highly efficient approach is to use a two-phase greedy algorithm. First, we construct the lexicographically smallest candidate string based on the properties of the `lcp` matrix. Second, we perform a full verification to check if this candidate string is indeed valid. If it is, it must be the answer. If not, no solution exists.
**Time:** O(n^2) · **Space:** O(n^2) or O(n)
**Pros:** Very efficient with a polynomial time complexity.; The greedy strategy is guaranteed to find the lexicographically smallest candidate.; The verification step is robust and ensures the candidate is correct.
**Cons:** Requires a full O(n^2) verification phase after construction.; The logic relies on two separate phases (construction and verification), which might seem less direct than a single-pass algorithm.
### Explanation
This approach is broken down into two main parts: construction and verification. It's also good practice to perform some initial sanity checks on the input matrix.

**Initial Sanity Checks (Optional but Recommended):**
Before starting, we can check for basic properties that any valid `lcp` matrix must have:
- `lcp[i][i] == n - i` for all `i`.
- The matrix must be symmetric: `lcp[i][j] == lcp[j][i]`.
- The LCP value cannot exceed the length of the suffixes: `lcp[i][j] <= n - max(i, j)`.
If any of these fail, we can immediately return an empty string.

**Phase 1: Greedy Construction**
To find the lexicographically smallest string, we should use the smallest characters ('a', 'b', 'c', ...) as early as possible. We iterate through the string positions from left to right (`i = 0 to n-1`). If the character at the current position `word[i]` hasn't been determined yet, we assign it the next available character from the alphabet. This assignment creates a new character group. The `lcp` matrix tells us which other indices must belong to the same group. Specifically, if `lcp[i][j] > 0`, then `word[j]` must equal `word[i]`. We enforce this by assigning the same character to all such `j`'s.

```java
public String findString(int[][] lcp) {
    int n = lcp.length;
    char[] word = new char[n];
    char nextChar = 'a';

    for (int i = 0; i < n; i++) {
        if (word[i] == 0) { // Character not yet assigned
            if (nextChar > 'z') {
                return ""; // Need more than 26 distinct characters
            }
            word[i] = nextChar;
            for (int j = i + 1; j < n; j++) {
                if (lcp[i][j] > 0) {
                    word[j] = nextChar;
                }
            }
            nextChar++;
        }
    }
```

**Phase 2: Verification**
The candidate string is built by only considering if `lcp[i][j]` is zero or non-zero. We must now verify the exact values. We do this by computing the LCP matrix for our generated `word` and comparing it to the input `lcp` matrix. This can be done efficiently with dynamic programming.

We iterate backwards from the end of the string. The LCP of two suffixes `word[i...]` and `word[j...]` is 0 if `word[i] != word[j]`. If `word[i] == word[j]`, it is `1 +` the LCP of the rest of the suffixes, `word[i+1...]` and `word[j+1...]`.

```java
    // Verification Phase
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int currentLcp;
            if (word[i] != word[j]) {
                currentLcp = 0;
            } else {
                if (i == n - 1 || j == n - 1) {
                    currentLcp = 1;
                } else {
                    currentLcp = 1 + lcp[i + 1][j + 1];
                }
            }
            if (lcp[i][j] != currentLcp) {
                return "";
            }
        }
    }
    // A more robust way is to recompute from scratch
    int[][] computedLcp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (word[i] == word[j]) {
                computedLcp[i][j] = 1;
                if (i + 1 < n && j + 1 < n) {
                    computedLcp[i][j] += computedLcp[i + 1][j + 1];
                }
            }
            if (computedLcp[i][j] != lcp[i][j]) {
                return "";
            }
        }
    }

    return new String(word);
}
```
This combined approach correctly and efficiently finds the solution.
### Algorithm
- Get the size of the matrix, `n`.
- **Greedy Construction:**
  - Initialize a character array `word` of size `n` and a character `nextChar = 'a'`.
  - Iterate `i` from `0` to `n-1`:
    - If `word[i]` has not been assigned a character yet:
      - If `nextChar > 'z'`, return `""` as more than 26 unique characters are needed.
      - Assign `word[i] = nextChar`.
      - For all `j > i`, if `lcp[i][j] > 0`, it implies `word[j]` must be the same as `word[i]`. Assign `word[j] = nextChar`.
      - Increment `nextChar`.
- **Verification:**
  - The constructed `word` is the only candidate for the lexicographically smallest solution. Now, we must verify it.
  - Create a new `n x n` matrix, `computedLcp`.
  - Fill `computedLcp` using dynamic programming, iterating `i` and `j` from `n-1` down to `0`:
    - If `word[i] == word[j]`, `computedLcp[i][j] = 1 + (i+1 < n && j+1 < n ? computedLcp[i+1][j+1] : 0)`.
    - Otherwise, `computedLcp[i][j] = 0`.
  - During the computation, if at any point `computedLcp[i][j]` does not match the input `lcp[i][j]`, the candidate is invalid. Return `""`.
- If the entire verification process completes without returning, the candidate string is valid. Return it.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string findTheString(vector<vector<int>> &lcp) {
    int i = 0, n = lcp.size();
    string s(n, '\0');
    for (char c = 'a'; c <= 'z'; ++c) {
      while (i < n && s[i]) {
        ++i;
      }
      if (i == n) {
        break;
      }
      for (int j = i; j < n; ++j) {
        if (lcp[i][j]) {
          s[j] = c;
        }
      }
    }
    if (s.find('\0') != -1) {
      return "";
    }
    for (i = n - 1; ~i; --i) {
      for (int j = n - 1; ~j; --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]) {
          return "";
        }
      }
    }
    return s;
  }
};

```

### Python

```python
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)

```