Longest common prefix between adjacent strings after removals

Array String

32.3% acceptance

Feb 25, 2026

You are given an array of strings words. For each index i, remove words[i] and compute the length of the longest common prefix among all adjacent pairs in the modified array. Return an array answer where answer[i] is the result.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_common_prefix(words: Vec<String>) -> Vec<i32> {
    let n = words.len();
    if n == 1 {
      return vec![0];
    }

    // Precompute lcp between adjacent pairs: lcp[i] = LCP(words[i], words[i+1]) for i in 0..n-1
    let lcp_adj: Vec<i32> = (0..n - 1)
      .map(|i| {
        let a = words[i].as_bytes();
        let b = words[i + 1].as_bytes();
        let mut k = 0;
        while k < a.len() && k < b.len() && a[k] == b[k] {
          k += 1;
        }
        k as i32
      })
      .collect();

    // When removing index i from words, the adjacent pairs change:
    // - Original pairs (i-1, i) and (i, i+1) are removed.
    // - New pair (i-1, i+1) is added (if both exist).
    // All other pairs remain. We need the maximum over all remaining pairs.

    // Precompute prefix max and suffix max of lcp_adj
    // prefix_max[i] = max of lcp_adj[0..=i]
    // suffix_max[i] = max of lcp_adj[i..n-1]

    let mut prefix_max = vec![0i32; n - 1];
    prefix_max[0] = lcp_adj[0];
    for i in 1..n - 1 {
      prefix_max[i] = prefix_max[i - 1].max(lcp_adj[i]);
    }

    let mut suffix_max = vec![0i32; n - 1];
    suffix_max[n - 2] = lcp_adj[n - 2];
    for i in (0..n - 2).rev() {
      suffix_max[i] = suffix_max[i + 1].max(lcp_adj[i]);
    }

    // max of all pairs except those involving index i:
    // Pairs involving i: (i-1, i) = lcp_adj[i-1] and (i, i+1) = lcp_adj[i]
    // But note lcp_adj[j] = LCP(words[j], words[j+1]).
    // When removing i: pairs to exclude are lcp_adj[i-1] (if i>0) and lcp_adj[i] (if i<n-1).
    // We include pairs [0, i-2] and [i+1, n-2] from original, plus new pair (i-1, i+1) if both exist.

    let lcp_of = |a: &str, b: &str| -> i32 {
      let ab = a.as_bytes();
      let bb = b.as_bytes();
      let mut k = 0;
      while k < ab.len() && k < bb.len() && ab[k] == bb[k] {
        k += 1;
      }
      k as i32
    };

    let mut ans = vec![0i32; n];
    for i in 0..n {
      let mut best = 0i32;

      // Pairs from [0..i-2] (original lcp_adj[0..=i-2])
      if i >= 2 {
        best = best.max(prefix_max[i - 2]);
      }
      // Pairs from [i+1..n-2] (original lcp_adj[i+1..=n-2])
      if i + 1 <= n - 2 {
        best = best.max(suffix_max[i + 1]);
      }
      // New pair (i-1, i+1)
      if i > 0 && i < n - 1 {
        best = best.max(lcp_of(&words[i - 1], &words[i + 1]));
      }

      ans[i] = best;
    }

    ans
  }
}