Find the string with lcp

Array String Dynamic Programming Greedy Union-Find Matrix

32.5% acceptance

Feb 25, 2026

206

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'.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_the_string(lcp: Vec<Vec<i32>>) -> String {
    let n = lcp.len();

    // Assign characters greedily
    let mut word = vec![0u8; n]; // 0 = unassigned, 1..=26 = 'a'..'z'
    let mut next_char = 1u8;
    for i in 0..n {
      if word[i] == 0 {
        if next_char > 26 { return String::new(); }
        word[i] = next_char;
        next_char += 1;
      }
      // Propagate to all j > i where lcp[i][j] > 0
      for j in i + 1..n {
        if lcp[i][j] > 0 {
          if word[j] == 0 {
            word[j] = word[i];
          } else if word[j] != word[i] {
            return String::new(); // contradiction
          }
        } else {
          // lcp[i][j] == 0: must have word[i] != word[j]
          if word[j] != 0 && word[j] == word[i] {
            return String::new(); // contradiction
          }
        }
      }
    }

    // Verify lcp matrix by computing expected lcp from word
    // expected[i][j] = 1 + expected[i+1][j+1] if word[i]==word[j], else 0
    let mut expected = vec![vec![0i32; n]; n];
    for i in (0..n).rev() {
      for j in (0..n).rev() {
        if word[i] == word[j] {
          expected[i][j] = 1 + if i + 1 < n && j + 1 < n { expected[i + 1][j + 1] } else { 0 };
        } else {
          expected[i][j] = 0;
        }
        if expected[i][j] != lcp[i][j] {
          return String::new();
        }
      }
    }

    word.iter().map(|&c| (b'a' + c - 1) as char).collect()
  }
}