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.
Example 1:
Input: s = "madxa", t = "madam"
Output: 4
Explanation:
Removing s[3] from s results in "mada", which has a longest common prefix of length 4 with t.
Example 2:
Input: s = "leetcode", t = "eetcode"
Output: 7
Explanation:
Removing s[0] from s results in "eetcode", which matches t.
Example 3:
Input: s = "one", t = "one"
Output: 3
Explanation:
No removal is needed.
Example 4:
Input: s = "a", t = "b"
Output: 0
Explanation:
s and t cannot have a common prefix.
Constraints:
1 <= s.length <= 1051 <= t.length <= 105s and t contain only lowercase English letters.Problem Overview: You are given two strings and need the maximum length of their common prefix if you are allowed to remove at most one character from either string. The goal is to simulate the comparison carefully so a single mismatch can be skipped while still maximizing the prefix length.
Approach 1: Brute Force Removal Simulation (O(n2) time, O(1) space)
Try every possible removal position in the first string and recompute the common prefix against the second string. Repeat the same by removing each position in the second string. For every candidate string, iterate character by character until a mismatch occurs and record the prefix length. This approach directly simulates the rule but repeatedly scans the strings, leading to quadratic time in the worst case.
Approach 2: Two Pointers with One Skip (O(n) time, O(1) space)
Traverse both strings using two pointers. As long as characters match, move both pointers forward and extend the prefix. When the first mismatch appears, simulate the single allowed removal by checking two possibilities: skip the current character in the first string or skip the current character in the second string. Continue matching from those positions and compute the resulting prefix length for each case. The key insight is that only the first mismatch matters because only one removal is allowed.
This strategy uses the two pointers technique to scan both strings in linear time. Each pointer moves forward without backtracking, and the mismatch branch is evaluated only once. The solution works well because the problem is essentially a controlled comparison of two string sequences with a single allowed deviation.
Recommended for interviews: Interviewers expect the O(n) two‑pointer approach. The brute force version demonstrates understanding of the constraint (removing one character), but the optimized scan shows you can convert the idea into a linear pass using two pointers. This is the pattern commonly used in string comparison problems where limited edits are allowed.
We record the lengths of the strings s and t as n and m, respectively. Then, we use two pointers i and j to point to the beginning of the strings s and t, and use a boolean variable rem to record whether a character has been removed.
Next, we start traversing the strings s and t. If s[i] is not equal to t[j], we check if a character has already been removed. If a character has been removed, we exit the loop; otherwise, we mark that a character has been removed and skip s[i]. Otherwise, we skip both s[i] and t[j]. Continue traversing until i geq n or j geq m.
Finally, return j.
The time complexity is O(n+m), where n and m are the lengths of the strings s and t, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Removal Simulation | O(n²) | O(1) | Useful for understanding the problem or when string size is very small |
| Two Pointers with One Skip | O(n) | O(1) | Optimal solution for large inputs and typical interview expectations |
Practice Longest Common Prefix After at Most One Removal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor