Longest common prefix after at most one removal

Two Pointers String

67.3% acceptance

Mar 31, 2026

You are given two strings s and t. Return the length of the longest common prefix between s and t after removing at most one character from s. Note: s can be left without any removal.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn longest_common_prefix(s: String, t: String) -> i32 {
    let sb = s.as_bytes();
    let tb = t.as_bytes();
    // First, find common prefix without removal
    let mut i = 0;
    while i < sb.len() && i < tb.len() && sb[i] == tb[i] {
      i += 1;
    }
    // Try no removal: prefix length = i
    let mut best = i;
    // Try removing character at position i from s (the first mismatch in s)
    // After removing sb[i], s becomes sb[0..i] + sb[i+1..]
    // The prefix sb[0..i] already matches tb[0..i]
    // Now compare sb[i+1..] with tb[i..]
    if i < sb.len() {
      let mut j = i + 1;
      let mut k = i;
      while j < sb.len() && k < tb.len() && sb[j] == tb[k] {
        j += 1;
        k += 1;
      }
      best = best.max(k);
    }
    best as i32
  }
}