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 <= 1051 <= t.length <= 105s and t contain only lowercase English letters.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 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++
Go
TypeScript
Rust
JavaScript
Practice Longest Common Prefix After at Most One Removal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor