Minimum Deletions to Form a Subsequence

You are given two strings, \(S\) and \(W\). Your task is to determine the minimum number of deletions required from \(S\) so that the string \(W\) appears as a subsequence of \(S\). If it is impossible to obtain \(W\) as a subsequence of \(S\), print -1.

Recall that a string \(W\) is a subsequence of \(S\) if \(W\) can be obtained from \(S\) by deleting some (possibly zero) characters without changing the order of the remaining characters. Formally, if \(|S|\) and \(|W|\) denote the lengths of \(S\) and \(W\) respectively, then if \(W\) is a subsequence of \(S\), the minimum number of deletions is \(|S| - |W|\).

Examples:

• For \(S = \texttt{abcde}\) and \(W = \texttt{ace}\), the answer is \(2\), as deleting \(\texttt{b}\) and \(\texttt{d}\) yields \(\texttt{ace}\).
• For \(S = \texttt{abcde}\) and \(W = \texttt{aec}\), the answer is \(-1\), because \(\texttt{aec}\) is not a subsequence of \(\texttt{abcde}\).

inputFormat

The input consists of two lines:

1. The first line contains the string \(S\).
2. The second line contains the string \(W\).

Both strings may consist of lowercase letters. There will be no extra spaces.

outputFormat

Output a single integer, representing the minimum number of deletions required from \(S\) to obtain \(W\) as a subsequence. If \(W\) cannot be formed, output \(-1\).

abcde
ace

2