Append the fewest characters to the end of one string so another string becomes its subsequence.
Given two strings s and t, you may append characters only to the end of s. Determine the minimum number of characters that must be appended so that t becomes a subsequence of the resulting string.
A string x is a subsequence of a string y if x can be formed by deleting zero or more characters from y without changing the order of the remaining characters.
Input Format
- Two strings
sandt. - You may assume both strings contain lowercase English letters in the standard formulation.
Output Format
- Return the minimum number of characters that need to be appended to
sso thattis a subsequence of the final string.
Constraints
0 <= |s|, |t|.- The intended solution should run in linear time with respect to the string lengths.
- In the common interview/LeetCode formulation, both strings are non-empty and contain lowercase letters.
Example 1
Input
s = "coaching", t = "coding"
Output
4
Explanation
The longest prefix of t that appears as a subsequence of s is "co". The remaining 4 characters "ding" must be appended.
Example 2
Input
s = "abcde", t = "aebdc"
Output
3
Explanation
The subsequence match can cover "ab" from t, leaving "dc"? Wait, because order must be preserved. The longest matched prefix is "ae"? No. For this input, the minimum appended characters is 3 because only the prefix "ab" can be matched before t runs ahead.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.