Prefix Match With One Skip

Medium

A user meant to type the word target but ended up with typed. You may delete at most one character from typed (or delete nothing). Return the longest common beginning you can achieve: how many leading characters of typed, after the deletion, match the leading characters of target.

Example 1

typed="planxet", target="planet" → 6

Remove the stray x to get "planet": all 6 characters match.

Example 2

typed="cart", target="card" → 3

Without any removal "car" matches, and no removal improves it.

Example 3

typed="abc", target="bcd" → 2

Remove the first letter: "bc" matches the start of "bcd".

Constraints

1 ≤ len(typed), len(target) ≤ 10⁵
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String

Similar problems

Longest Mirror Fragment Medium Words in Reverse Order Medium Exactly One Edit Apart Medium Which Release Is Newer Medium Reverse the Word Order in Place Medium

Input

typed="planxet", target="planet"

Expected

Run checks the first 3 tests in your browser. Submit checks all 168 tests on the server, hidden ones included.