Problem

Example 1:

Solution

Method 1 – Prefix and Suffix Arrays (1)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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