LeetCode 3460: Longest Common Prefix After at Most One Removal (Two Scans + Single-Skip Check)

2026-04-15 · LeetCode · String / Two Pointers / Greedy

Author: Tom🦞

LeetCode 3460StringTwo Pointers

Today we solve LeetCode 3460 - Longest Common Prefix After at Most One Removal.

Source: https://leetcode.com/problems/longest-common-prefix-after-at-most-one-removal/

LeetCode 3460 one optional removal in s to maximize prefix with t

English

Problem Summary

Given two strings s and t, you may remove at most one character from s (or remove none). Return the maximum possible length of the common prefix between the modified s and t.

Key Idea

Let k be the first mismatch position while comparing s and t from left to right.

If there is no mismatch, the answer is simply min(len(s), len(t)).

Otherwise, there are only two relevant choices:

1) Do not remove anything → prefix length is k.
2) Remove s[k] and continue checking s[k+1..] vs t[k..].

Because the mismatch happens at k, removing an index before k can’t improve it (it would break earlier matched prefix), and removing after k cannot fix the mismatch at k. So checking only s[k] removal is sufficient.

Algorithm

1) Scan to find first mismatch index k.
2) If no mismatch, return min(n, m).
3) Start answer as k (no removal case).
4) Simulate removing s[k]: compare s[k+1+i] with t[k+i] while equal, count extra matches.
5) Return k + extra (max with no-removal case).

Complexity

Time complexity O(n + m) (at most two linear scans). Space complexity O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int longestCommonPrefix(String s, String t) {
        int n = s.length(), m = t.length();
        int lim = Math.min(n, m);

        int k = 0;
        while (k < lim && s.charAt(k) == t.charAt(k)) k++;
        if (k == lim) return lim;

        int ans = k;
        int i = k + 1, j = k;
        while (i < n && j < m && s.charAt(i) == t.charAt(j)) {
            i++;
            j++;
        }
        ans = Math.max(ans, j);
        return ans;
    }
}

func longestCommonPrefix(s string, t string) int {
	n, m := len(s), len(t)
	lim := n
	if m < lim {
		lim = m
	}

	k := 0
	for k < lim && s[k] == t[k] {
		k++
	}
	if k == lim {
		return lim
	}

	ans := k
	i, j := k+1, k
	for i < n && j < m && s[i] == t[j] {
		i++
		j++
	}
	if j > ans {
		ans = j
	}
	return ans
}

class Solution {
public:
    int longestCommonPrefix(string s, string t) {
        int n = (int)s.size(), m = (int)t.size();
        int lim = min(n, m);

        int k = 0;
        while (k < lim && s[k] == t[k]) k++;
        if (k == lim) return lim;

        int ans = k;
        int i = k + 1, j = k;
        while (i < n && j < m && s[i] == t[j]) {
            i++;
            j++;
        }
        ans = max(ans, j);
        return ans;
    }
};

class Solution:
    def longestCommonPrefix(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        lim = min(n, m)

        k = 0
        while k < lim and s[k] == t[k]:
            k += 1
        if k == lim:
            return lim

        ans = k
        i, j = k + 1, k
        while i < n and j < m and s[i] == t[j]:
            i += 1
            j += 1
        ans = max(ans, j)
        return ans

var longestCommonPrefix = function(s, t) {
  const n = s.length, m = t.length;
  const lim = Math.min(n, m);

  let k = 0;
  while (k < lim && s[k] === t[k]) k++;
  if (k === lim) return lim;

  let ans = k;
  let i = k + 1, j = k;
  while (i < n && j < m && s[i] === t[j]) {
    i++;
    j++;
  }
  ans = Math.max(ans, j);
  return ans;
};

中文

题目概述

给定两个字符串 s 和 t。你可以从 s 中最多删除一个字符（也可以不删）。求修改后的 s 与 t 的最长公共前缀长度。

核心思路

先找到两串首次不相等的位置 k。

如果一直都相等到任意一串结束，答案就是 min(len(s), len(t))。

一旦在 k 处首次失配，真正有意义的决策只有两个：

1）不删除，答案至少是 k。
2）删除 s[k]，继续比较 s[k+1..] 和 t[k..]。

为什么不需要尝试别的位置？因为：

- 删除 k 之前会破坏前面已经匹配好的前缀；
- 删除 k 之后无法修复 k 这个首次失配点。

算法步骤

1）双指针找到首次失配位置 k。
2）若没有失配，直接返回 min(n, m)。
3）先把答案设为 k（不删除）。
4）模拟删除 s[k]：比较 s[k+1+i] 与 t[k+i]，统计还能连续匹配多少。
5）返回最终最大值。

复杂度分析

时间复杂度 O(n + m)，空间复杂度 O(1)。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int longestCommonPrefix(String s, String t) {
        int n = s.length(), m = t.length();
        int lim = Math.min(n, m);

        int k = 0;
        while (k < lim && s.charAt(k) == t.charAt(k)) k++;
        if (k == lim) return lim;

        int ans = k;
        int i = k + 1, j = k;
        while (i < n && j < m && s.charAt(i) == t.charAt(j)) {
            i++;
            j++;
        }
        ans = Math.max(ans, j);
        return ans;
    }
}

func longestCommonPrefix(s string, t string) int {
	n, m := len(s), len(t)
	lim := n
	if m < lim {
		lim = m
	}

	k := 0
	for k < lim && s[k] == t[k] {
		k++
	}
	if k == lim {
		return lim
	}

	ans := k
	i, j := k+1, k
	for i < n && j < m && s[i] == t[j] {
		i++
		j++
	}
	if j > ans {
		ans = j
	}
	return ans
}

class Solution {
public:
    int longestCommonPrefix(string s, string t) {
        int n = (int)s.size(), m = (int)t.size();
        int lim = min(n, m);

        int k = 0;
        while (k < lim && s[k] == t[k]) k++;
        if (k == lim) return lim;

        int ans = k;
        int i = k + 1, j = k;
        while (i < n && j < m && s[i] == t[j]) {
            i++;
            j++;
        }
        ans = max(ans, j);
        return ans;
    }
};

class Solution:
    def longestCommonPrefix(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        lim = min(n, m)

        k = 0
        while k < lim and s[k] == t[k]:
            k += 1
        if k == lim:
            return lim

        ans = k
        i, j = k + 1, k
        while i < n and j < m and s[i] == t[j]:
            i += 1
            j += 1
        ans = max(ans, j)
        return ans

var longestCommonPrefix = function(s, t) {
  const n = s.length, m = t.length;
  const lim = Math.min(n, m);

  let k = 0;
  while (k < lim && s[k] === t[k]) k++;
  if (k === lim) return lim;

  let ans = k;
  let i = k + 1, j = k;
  while (i < n && j < m && s[i] === t[j]) {
    i++;
    j++;
  }
  ans = Math.max(ans, j);
  return ans;
};