We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Common Prefix After at Most One Removal

Number: 3796

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given two strings s and t, determine the length of the longest common prefix after removing at most one character from s. The removal is optional; you may choose to not remove any character if s already aligns well with t.

Key Insights

  • The obvious approach is to first match s and t from the beginning.
  • When a mismatch occurs at position i, you can consider removing s[i] (the first differing character) to potentially extend the common prefix.
  • Only one removal is allowed, so the removal must occur at the first mismatch to maximize the prefix length.
  • Use two pointers to simulate the matching process: one pointer for t and two for s (one for before removal and one for after removal).

Space and Time Complexity

Time Complexity: O(n) where n is the length of the strings (in the worst case, you scan both fully). Space Complexity: O(1) as only a few extra variables are used.

Solution

We start by comparing s and t character by character from the beginning. Let i be the index up to which the characters match. If we reach the end of one string, then the answer is simply the length of the matched portion. When a mismatch s[i] != t[i] occurs, we have one chance to remove a character from s. The best candidate for removal is at index i since the prefix up to i is already matching. After removing s[i], we set two pointers: one (j) to continue from s[i+1] and one (k) to continue from t[i]. We then further match until a mismatch occurs or end of either string is reached. The candidate longest prefix becomes the sum of the initially matched characters (i) plus the count of matching characters after the removal. Finally, the answer is the maximum of the prefix without removal and the prefix obtained after the potential removal.

Code Solutions

# Python solution with line-by-line comments

def longest_common_prefix_after_removal(s: str, t: str) -> int:
    # Determine initial common prefix length without any removal
    i = 0
    while i < len(s) and i < len(t) and s[i] == t[i]:
        i += 1
    # If entire prefix is matched or one string ended, return the matched length
    if i == len(s) or i == len(t):
        return i

    # Candidate using one removal at the first mismatch position (remove s[i])
    j, k = i + 1, i  # j for s (skipping the mismatched character), k for t
    while j < len(s) and k < len(t) and s[j] == t[k]:
        j += 1
        k += 1
    candidate_removal = i + (k - i)

    # The answer is the maximum of no removal (i) and removing one character from s.
    return max(i, candidate_removal)

# Example usage:
print(longest_common_prefix_after_removal("madxa", "madam"))  # Expected output: 4
print(longest_common_prefix_after_removal("leetcode", "eetcode"))  # Expected output: 7
print(longest_common_prefix_after_removal("one", "one"))  # Expected output: 3
print(longest_common_prefix_after_removal("a", "b"))  # Expected output: 0
← Back to All Questions