Longest Common Prefix After at Most One Removal

Problem

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.

Examples

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

Solution

Method 1 – Prefix and Suffix Arrays

Intuition

To find the longest common prefix after removing at most one string, we can precompute the common prefix for all prefixes and suffixes. For each string, consider removing it and compute the intersection of the prefix before and after it.

Approach

1. Let n be the number of strings. Compute pre[i] as the common prefix of strings 0..i-1 and suf[i] as the common prefix of strings i..n-1.
2. For each index i, the answer after removing string i is the common prefix of pre[i] and suf[i+1].
3. The final answer is the maximum length among all such prefixes.

Code

C++

class Solution {
public:
    string longestCommonPrefixAfterRemoval(vector<string>& arr) {
        int n = arr.size();
        vector<string> pre(n+1), suf(n+1);
        pre[0] = suf[n] = "";
        for (int i = 0; i < n; ++i) {
            pre[i+1] = commonPrefix(pre[i], arr[i]);
        }
        for (int i = n-1; i >= 0; --i) {
            suf[i] = commonPrefix(suf[i+1], arr[i]);
        }
        string ans = "";
        for (int i = 0; i < n; ++i) {
            string p = commonPrefix(pre[i], suf[i+1]);
            if (p.size() > ans.size()) ans = p;
        }
        return ans;
    }
    string commonPrefix(const string& a, const string& b) {
        int i = 0;
        while (i < a.size() && i < b.size() && a[i] == b[i]) i++;
        return a.substr(0, i);
    }
};

Go

func longestCommonPrefixAfterRemoval(arr []string) string {
    n := len(arr)
    pre := make([]string, n+1)
    suf := make([]string, n+1)
    pre[0], suf[n] = "", ""
    for i := 0; i < n; i++ {
        pre[i+1] = commonPrefix(pre[i], arr[i])
    }
    for i := n-1; i >= 0; i-- {
        suf[i] = commonPrefix(suf[i+1], arr[i])
    }
    ans := ""
    for i := 0; i < n; i++ {
        p := commonPrefix(pre[i], suf[i+1])
        if len(p) > len(ans) {
            ans = p
        }
    }
    return ans
}
func commonPrefix(a, b string) string {
    i := 0
    for i < len(a) && i < len(b) && a[i] == b[i] {
        i++
    }
    return a[:i]
}

Java

class Solution {
    public String longestCommonPrefixAfterRemoval(String[] arr) {
        int n = arr.length;
        String[] pre = new String[n+1], suf = new String[n+1];
        pre[0] = ""; suf[n] = "";
        for (int i = 0; i < n; i++) pre[i+1] = commonPrefix(pre[i], arr[i]);
        for (int i = n-1; i >= 0; i--) suf[i] = commonPrefix(suf[i+1], arr[i]);
        String ans = "";
        for (int i = 0; i < n; i++) {
            String p = commonPrefix(pre[i], suf[i+1]);
            if (p.length() > ans.length()) ans = p;
        }
        return ans;
    }
    private String commonPrefix(String a, String b) {
        int i = 0;
        while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) i++;
        return a.substring(0, i);
    }
}

Kotlin

class Solution {
    fun longestCommonPrefixAfterRemoval(arr: Array<String>): String {
        val n = arr.size
        val pre = Array(n+1) { "" }
        val suf = Array(n+1) { "" }
        for (i in 0 until n) pre[i+1] = commonPrefix(pre[i], arr[i])
        for (i in n-1 downTo 0) suf[i] = commonPrefix(suf[i+1], arr[i])
        var ans = ""
        for (i in 0 until n) {
            val p = commonPrefix(pre[i], suf[i+1])
            if (p.length > ans.length) ans = p
        }
        return ans
    }
    private fun commonPrefix(a: String, b: String): String {
        var i = 0
        while (i < a.length && i < b.length && a[i] == b[i]) i++
        return a.substring(0, i)
    }
}

Python

class Solution:
    def longestCommonPrefixAfterRemoval(self, arr: list[str]) -> str:
        n = len(arr)
        pre = [""] * (n+1)
        suf = [""] * (n+1)
        for i in range(n):
            pre[i+1] = self.commonPrefix(pre[i], arr[i])
        for i in range(n-1, -1, -1):
            suf[i] = self.commonPrefix(suf[i+1], arr[i])
        ans = ""
        for i in range(n):
            p = self.commonPrefix(pre[i], suf[i+1])
            if len(p) > len(ans):
                ans = p
        return ans
    def commonPrefix(self, a: str, b: str) -> str:
        i = 0
        while i < len(a) and i < len(b) and a[i] == a
{{< /code_tabs >}}