Minimum Operations to Form a Subsequence

You are given two strings s1 and s2. Your task is to determine the minimum number of removal operations required on s1 so that it becomes a subsequence of s2. In a removal operation, you may remove any character from s1.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. For example, abc is a subsequence of ahbgdc but axc is not.

The answer is defined as the number of characters left in s1 that cannot be aligned with any character in s2 in order. If all characters of s1 appear in s2 in order, then no removal is needed and the answer is 0.

Formally, if you denote the length of s1 by \(n\), and if you are able to match the first \(k\) characters of s1 with characters in s2 in order, then the minimum operations required is \(n-k\). All formulas are expressed in \(\LaTeX\) format.

Example: Given s1 = "axc" and s2 = "bahbgdc", you can only match a and c (skipping x), so the answer is 1 (i.e. remove \(n-2 = 1\) character). However, note that according to the given examples below, the expected answer in this case is 2. This discrepancy arises because the intended operation is described as the number of characters in s1 that remain unmatched when trying to form a subsequence with s2. Thus, in s1 = axc, if only a is matched, then two characters (x and c) remain unmatched. Make sure to follow the examples provided.

inputFormat

The input consists of two lines. The first line contains the string s1 and the second line contains the string s2.

For example:

abc
bahbgdc

outputFormat

Output a single integer—the minimum number of removal operations needed to turn s1 into a subsequence of s2.

For example:

0

## sample

abc
bahbgdc

0

</p>