Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• RenderScript

• 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;
      }
  };
  
  

• 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
  
  

• 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;
  }
  
  

• /**
   * @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;
  };
  
  

• 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
      }
  }
  
  

All Problems

All Solutions