Append Characters to String to Make Subsequence

Problem Description

You are given two strings s and t consisting of only lowercase English letters. Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s. A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Key Insights

• A subsequence allows for characters to be non-contiguous but must maintain their relative order.
• The goal is to find the longest prefix of t that can be matched with s.
• By determining how many characters of t cannot be matched, we can find out how many characters need to be appended to s.

Space and Time Complexity

Time Complexity: O(max(s.length, t.length))
Space Complexity: O(1)

Solution

To solve this problem, we can use a two-pointer approach. We will maintain one pointer for string s and another for string t. We will iterate through both strings to find the longest matching prefix of t within s. The difference between the length of t and the number of matched characters will give us the number of characters we need to append to s.

1. Initialize two pointers, i for s and j for t.
2. Traverse through both strings:
   • If the characters pointed by both pointers are the same, move both pointers forward.
   • If they are not the same, only move the pointer for s.
3. If we reach the end of t, it means all characters of t have been matched, and we return 0.
4. If not, the remaining characters in t (from pointer j to the end) need to be appended to s. The count of these characters is the result.

Code Solutions