3460. Longest Common Prefix After at Most One Removal 🔒

Description

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.

Solutions

Solution 1: Two Pointers

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 \(\textit{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.

Python3JavaC++GoTypeScriptRustJavaScript

class Solution:
    def longestCommonPrefix(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        i = j = 0
        rem = False
        while i < n and j < m:
            if s[i] != t[j]:
                if rem:
                    break
                rem = True
            else:
                j += 1
            i += 1
        return j

class Solution {
    public int longestCommonPrefix(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        boolean rem = false;
        while (i < n && j < m) {
            if (s.charAt(i) != t.charAt(j)) {
                if (rem) {
                    break;
                }
                rem = true;
            } else {
                ++j;
            }
            ++i;
        }
        return j;
    }
}

class Solution {
public:
    int longestCommonPrefix(string s, string t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        bool rem = false;
        while (i < n && j < m) {
            if (s[i] != t[j]) {
                if (rem) {
                    break;
                }
                rem = true;
            } else {
                ++j;
            }
            ++i;
        }
        return j;
    }
};

func longestCommonPrefix(s string, t string) int {
    n, m := len(s), len(t)
    i, j := 0, 0
    rem := false
    for i < n && j < m {
        if s[i] != t[j] {
            if rem {
                break
            }
            rem = true
        } else {
            j++
        }
        i++
    }
    return j
}

function longestCommonPrefix(s: string, t: string): number {
    const [n, m] = [s.length, t.length];
    let [i, j] = [0, 0];
    let rem: boolean = false;
    while (i < n && j < m) {
        if (s[i] !== t[j]) {
            if (rem) {
                break;
            }
            rem = true;
        } else {
            ++j;
        }
        ++i;
    }
    return j;
}

impl Solution {
    pub fn longest_common_prefix(s: String, t: String) -> i32 {
        let (n, m) = (s.len(), t.len());
        let (mut i, mut j) = (0, 0);
        let mut rem = false;

        while i < n && j < m {
            if s.as_bytes()[i] != t.as_bytes()[j] {
                if rem {
                    break;
                }
                rem = true;
            } else {
                j += 1;
            }
            i += 1;
        }

        j as i32
    }
}

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var longestCommonPrefix = function (s, t) {
    const [n, m] = [s.length, t.length];
    let [i, j] = [0, 0];
    let rem = false;
    while (i < n && j < m) {
        if (s[i] !== t[j]) {
            if (rem) {
                break;
            }
            rem = true;
        } else {
            ++j;
        }
        ++i;
    }
    return j;
};

Comments