Minimum Deletion Distance

Given two strings word1 and word2, your task is to compute the minimum number of deletion operations required to make the two strings identical. In one operation, you can delete exactly one character from either string.

This problem can be solved by finding the length of the longest common subsequence (LCS) between the two strings. Let \( l \) be the length of the LCS, and let \( m \) and \( n \) be the lengths of word1 and word2 respectively. The minimum number of deletions required is given by:

[ (m - l) + (n - l) ]

For example, for word1 = "sea" and word2 = "eat", the LCS is "ea" (of length 2) so the answer is \((3-2) + (3-2) = 2\).

inputFormat

The input consists of two lines:

• The first line contains the string word1.
• The second line contains the string word2.

Each string may contain only printable characters and can be empty.

outputFormat

Output a single integer which is the minimum number of deletion operations required to make the two strings identical.

sea
eat

2