A base assembly string a is fixed. You want string b to appear as a subsequence of a after you append some characters to the END of a (you may append any characters you like). Find the minimum number of characters that must be appended.
Equivalently, match the longest prefix of b that already appears as a subsequence of a; every remaining character of b must be appended.
Line 1: the base string a.
Line 2: the required string b.
A single integer: the minimum number of characters to append.
a <= 40b <= 40Example 1
Input
abc abcd
Expected
1
Explanation
a already contains a, b, c in order; only the final d must be appended, so the answer is 1.
Example 2
Input
xyz ab
Expected
2
Explanation
None of a, b can be matched inside xyz in order, so both must be appended: answer 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →