Skip to content

3460. Longest Common Prefix After at Most One Removal 👍

  • Time: $O(|\texttt{s}| + |\texttt{t}|)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int longestCommonPrefix(string s, string t) {
    int i = 0;  // s's index
    int j = 0;  // t's index
    bool canSkip = true;

    while (i < s.length() && j < t.length())
      if (s[i] == t[j]) {
        ++i;
        ++j;
      } else if (canSkip) {
        ++i;
        canSkip = false;
      } else {
        return j;
      }

    return j;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int longestCommonPrefix(String s, String t) {
    int i = 0; // s's index
    int j = 0; // t's index
    boolean canSkip = true;

    while (i < s.length() && j < t.length())
      if (s.charAt(i) == t.charAt(j)) {
        ++i;
        ++j;
      } else if (canSkip) {
        ++i;
        canSkip = false;
      } else {
        return j;
      }

    return j;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def longestCommonPrefix(self, s: str, t: str) -> int:
    i = 0  # s's index
    j = 0  # t's index
    canSkip = True

    while i < len(s) and j < len(t):
      if s[i] == t[j]:
        i += 1
        j += 1
      elif canSkip:
        i += 1
        canSkip = False
      else:
        return j

    return j