LeetCode 3460 - Longest Common Prefix After at Most One Removal

We are given two lowercase strings, s and t. We may remove at most one character from s. The removal is optional, so we are also allowed to leave s unchanged.

leetcodemediumtwo-pointersstring

LeetCode Problem 3460

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

LeetCode 3460 - Longest Common Prefix After at Most One Removal

Problem Understanding

We are given two lowercase strings, s and t.

We may remove at most one character from s. The removal is optional, so we are also allowed to leave s unchanged.

After performing zero or one removal, we want to compute the length of the longest common prefix between the resulting string and t.

A common prefix is the longest sequence of characters starting from index 0 that is identical in both strings. As soon as a mismatch occurs, the common prefix ends.

The task is to return the maximum possible common prefix length obtainable after removing at most one character from s.

For example, if:

  • s = "madxa"
  • t = "madam"

then removing 'x' from s produces "mada", whose first four characters match "mada" in t. Therefore the answer is 4.

The constraints are:

  • 1 <= len(s) <= 100000
  • 1 <= len(t) <= 100000

The strings can be very large, so any solution with quadratic behavior is too slow. We need a solution that runs in linear time.

Several edge cases are important:

  • The strings may already match perfectly, so no removal is needed.
  • The optimal removal may occur at the beginning of s.
  • The optimal removal may occur in the middle of s.
  • The optimal removal may occur near the end of s.
  • Removing a character may still not help at all.
  • One or both strings may have length 1.

The key challenge is determining whether skipping exactly one character in s can extend the matching prefix.

Approaches

Brute Force

A straightforward solution is to try every possible removal position.

For each index i in s:

  1. Remove s[i].
  2. Construct the resulting string.
  3. Compute the common prefix length with t.

We must also consider the case where no character is removed.

This approach is correct because it explicitly checks every valid operation and returns the best result.

However, if n = len(s), there are n + 1 possibilities. Computing the common prefix for each possibility can take O(n) time. Therefore the total complexity becomes O(n²), which is far too slow when n can reach 100000.

Optimal Observation

Since only one character may be removed, the matching process can encounter at most one mismatch that we choose to skip.

Suppose we scan both strings from left to right.

If characters match, we advance both pointers.

If we encounter the first mismatch, we have only one possible action:

  • Remove the current character from s.
  • Continue matching the remainder.

Any mismatch occurring after that immediately ends the common prefix because no additional removals are available.

Therefore we only need to find:

  1. The first position where s and t differ.
  2. How many additional characters match after skipping that character in s.

This can be done with a simple two pointer scan in linear time.

Comparison of Approaches

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Try every possible removal and recompute prefix
Optimal O(n) O(1) Find first mismatch, then simulate the single allowed skip

Algorithm Walkthrough

  1. Let n = len(s) and m = len(t).
  2. Start with an index i = 0.
  3. Move i forward while:
  • i < n
  • i < m
  • s[i] == t[i]

This finds the length of the common prefix before any mismatch occurs. 4. If i == min(n, m), then every character up to the shorter string matched.

Since removing a character cannot increase the common prefix beyond the available characters in t, the answer is simply i. 5. Otherwise, a mismatch occurs at position i. 6. Treat s[i] as the character we remove. Set:

  • j = i + 1 in s
  • k = i in t
  1. Continue matching while:
  • j < n
  • k < m
  • s[j] == t[k]

Advance both pointers for every successful match. 8. The common prefix length equals the final value of k, because k represents how many characters of t have been matched from the beginning. 9. Return k.

Why it works

Before the first mismatch, every valid common prefix must include all matching characters, so those characters are forced.

When the first mismatch occurs, the only possible beneficial operation is to remove the mismatching character from s. Removing any earlier character would destroy already matched prefix characters, and removing a later character would not fix the current mismatch. Therefore the optimal solution is uniquely determined at the first mismatch. After using the single removal, matching continues until another mismatch or until one string ends. This guarantees that the computed prefix length is the maximum achievable value.

Python Solution

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

        i = 0
        while i < n and i < m and s[i] == t[i]:
            i += 1

        if i == min(n, m):
            return i

        j = i + 1
        k = i

        while j < n and k < m and s[j] == t[k]:
            j += 1
            k += 1

        return k

The implementation first finds the longest matching prefix before any mismatch occurs. The variable i represents the first position where the strings differ.

If no mismatch exists within the overlapping portion of the strings, the answer is immediately known because removing a character cannot create a longer prefix than the entire matched region.

When a mismatch appears, the algorithm consumes the one allowed removal by skipping s[i]. The pointers j and k then continue comparing the remainder of the strings. The final value of k corresponds exactly to the number of prefix characters that match after the optimal removal.

The algorithm performs only sequential scans and never revisits characters.

Go Solution

func longestCommonPrefix(s string, t string) int {
	n, m := len(s), len(t)

	i := 0
	for i < n && i < m && s[i] == t[i] {
		i++
	}

	if i == min(n, m) {
		return i
	}

	j := i + 1
	k := i

	for j < n && k < m && s[j] == t[k] {
		j++
		k++
	}

	return k
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows exactly the same logic as the Python version. Since the input contains only lowercase English letters, indexing strings by byte is safe. No special handling for Unicode is required. All operations use integer indices, and there are no overflow concerns because string lengths are at most 100000.

Worked Examples

Example 1

Input

s = "madxa"
t = "madam"

Phase 1: Find First Mismatch

i s[i] t[i] Match?
0 m m Yes
1 a a Yes
2 d d Yes
3 x a No

Now:

i = 3

Remove s[3].

Phase 2: Continue Matching

Initial state:

j = 4
k = 3
j k s[j] t[k] Match?
4 3 a a Yes

After matching:

j = 5
k = 4

Loop ends.

Answer:

4

Example 2

Input

s = "leetcode"
t = "eetcode"

Phase 1

i s[i] t[i] Match?
0 l e No

First mismatch:

i = 0

Remove 'l'.

Phase 2

j k s[j] t[k] Match?
1 0 e e Yes
2 1 e e Yes
3 2 t t Yes
4 3 c c Yes
5 4 o o Yes
6 5 d d Yes
7 6 e e Yes

Final:

k = 7

Answer:

7

Example 3

Input

s = "one"
t = "one"

Phase 1

i s[i] t[i] Match?
0 o o Yes
1 n n Yes
2 e e Yes

Now:

i = 3

Since:

i == min(len(s), len(t))

Return:

3

Example 4

Input

s = "a"
t = "b"

Phase 1

i s[i] t[i] Match?
0 a b No

Remove 'a'.

Phase 2

j = 1
k = 0

The loop cannot run because j == len(s).

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each pointer moves forward at most once
Space O(1) Only a few integer variables are used

The first scan advances through the common prefix. The second scan processes the remaining suffix after the removal. Across both scans, every character is examined at most once, giving linear time complexity. No auxiliary data structures are required, so the space usage is constant.

Test Cases

sol = Solution()

assert sol.longestCommonPrefix("madxa", "madam") == 4      # remove in middle
assert sol.longestCommonPrefix("leetcode", "eetcode") == 7 # remove first char
assert sol.longestCommonPrefix("one", "one") == 3          # no removal needed
assert sol.longestCommonPrefix("a", "b") == 0             # no common prefix

assert sol.longestCommonPrefix("abc", "abc") == 3         # identical strings
assert sol.longestCommonPrefix("xabc", "abc") == 3        # remove first character
assert sol.longestCommonPrefix("abxc", "abc") == 3        # remove middle character
assert sol.longestCommonPrefix("abcdx", "abcd") == 4      # mismatch after full prefix
assert sol.longestCommonPrefix("abc", "abd") == 2         # removal does not help
assert sol.longestCommonPrefix("aaab", "aaaa") == 3       # mismatch near end
assert sol.longestCommonPrefix("z", "z") == 1             # single matching char
assert sol.longestCommonPrefix("ba", "a") == 1            # remove leading char
assert sol.longestCommonPrefix("abcdef", "abqdef") == 2   # second mismatch stops match
assert sol.longestCommonPrefix("cabc", "abc") == 3        # entire match after removal
assert sol.longestCommonPrefix("abc", "xyz") == 0         # completely different

Test Summary

Test Why
"madxa", "madam" Removal in the middle
"leetcode", "eetcode" Removal at index 0
"one", "one" No removal needed
"a", "b" Smallest mismatch case
"abc", "abc" Fully identical strings
"xabc", "abc" Remove first character
"abxc", "abc" Remove internal character
"abcdx", "abcd" Extra trailing character
"abc", "abd" Removal provides no benefit
"aaab", "aaaa" Mismatch near the end
"z", "z" Single character match
"ba", "a" Length reduction creates match
"abcdef", "abqdef" Second mismatch terminates prefix
"cabc", "abc" Complete alignment after removal
"abc", "xyz" No common prefix at all

Edge Cases

Removal at the First Character

A common source of bugs is assuming that matching must begin before a removal occurs. Consider s = "leetcode" and t = "eetcode". The optimal move is removing the very first character. The implementation handles this naturally because the first mismatch occurs at index 0, and the second phase begins with j = 1 and k = 0.

Strings Already Match Completely

When the strings are identical, there is no mismatch to trigger the removal logic. An incorrect implementation might unnecessarily remove a character and reduce the answer. The algorithm explicitly checks whether the entire overlapping region matched and immediately returns that length.

Removal Does Not Fix the Mismatch

Consider s = "abc" and t = "abd". The first mismatch occurs at index 2. Removing 'c' still does not create additional matching characters because s ends immediately afterward. The implementation correctly enters the second phase, performs no additional matches, and returns the existing prefix length of 2.

Single Character Strings

For inputs such as s = "a" and t = "b", the first mismatch occurs immediately and skipping the only character leaves an empty string. The loop conditions safely prevent out of bounds access, and the algorithm correctly returns 0.

Multiple Mismatches

Consider s = "abcdef" and t = "abqxyz". Only one removal is allowed. After skipping the first problematic character in s, another mismatch appears immediately. The algorithm stops at that point, correctly reflecting the fact that no second removal is available.