Erase Until the Words Match

Medium

You get two words first and second. In one step you may erase exactly one letter from either word; the remaining letters close the gap and keep their order. Return the smallest number of steps after which the two words are identical (two empty strings count as identical).

Example 1

first='stone', second='notes' → 6

The longest part both words can keep is one (or ote, and so on), three letters. Two letters go from each word, 4 in total.

Example 2

first='abc', second='abc' → 0

The words are already equal.

Example 3

first='mint', second='x' → 5

There are no common letters, so both words must be erased entirely: 4 + 1 = 5.

Constraints

1 ≤ len(first), len(second) ≤ 500
Words consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Letter Edits Medium Ways to Read a Digit Code Medium Weaving Two Strings Medium

Input

first='stone', second='notes'

Expected

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