Skip to main content
Talentd

Longest Common Prefix After at Most One Removal - Solution & Explanation

MediumPremiumFree on FleetCodeTwo PointersString10 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= t.length <= 105
  • s and t contain only lowercase English letters.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Removal SimulationO(n²)O(1)Useful for understanding the problem or when string size is very small
Two Pointers with One SkipO(n)O(1)Optimal solution for large inputs and typical interview expectations

Frequently Asked Questions

Is Longest Common Prefix After at Most One Removal easy or hard?
The problem is typically classified as Medium difficulty. The main challenge is recognizing that only the first mismatch matters and that you can simulate the allowed removal using two pointer branches instead of rebuilding strings.
Longest Common Prefix After at Most One Removal Python/Java solution
Most implementations follow the same logic across languages. Maintain two indices for the strings and track the first mismatch. After a mismatch, check both skip possibilities and compute the resulting prefix length. The algorithm translates directly to Python, Java, C++, Go, or JavaScript.
How to solve Longest Common Prefix After at Most One Removal in O(n)?
Use two pointers to scan both strings from left to right. When characters match, advance both pointers. When the first mismatch occurs, evaluate two scenarios: skip the character in the first string or skip the character in the second string. Continue matching from those positions and take the maximum prefix length.
What is the best approach for Longest Common Prefix After at Most One Removal?
The most efficient approach uses the two pointers technique. Traverse both strings together and stop at the first mismatch. At that point, simulate the single allowed removal by skipping a character in either string and continue matching. This runs in O(n) time with O(1) extra space.
Is Longest Common Prefix After at Most One Removal asked at Google/Amazon/Meta?
String comparison problems with limited edits are common in interviews at companies like Google, Amazon, and Meta. Variations appear in problems involving edit distance, prefix matching, or two‑pointer string validation. The pattern of handling a single allowed modification is frequently tested.
What data structure is used in Longest Common Prefix After at Most One Removal?
The solution mainly relies on basic string traversal with the two pointers technique. No advanced data structures are needed. The algorithm compares characters directly using indices while allowing one conditional skip.
What is the time complexity of Longest Common Prefix After at Most One Removal?
The optimal solution runs in O(n) time where n is the length of the shorter string. Each character is processed at most once while scanning both strings with two pointers. Space complexity remains O(1) because no additional data structures are required.

Ready to solve this problem?

Practice Longest Common Prefix After at Most One Removal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Common Prefix