Append Characters to String to Make Subsequence

Append Characters to String to Make Subsequence

What is this problem about?

The "Append Characters to String to Make Subsequence interview question" is a string matching challenge. You are given two strings, $s$ and $t$. Your goal is to find the minimum number of characters you need to append to the end of $s$ so that $t$ becomes a subsequence of $s$. A subsequence is a string derived by deleting zero or more characters from the original string without changing the order of the remaining characters.

Why is this asked in interviews?

Companies like Microsoft and Amazon ask the "Append Characters to String to Make Subsequence coding problem" to test a candidate's understanding of string traversal and the "Two Pointers interview pattern." It's an efficient way to evaluate if a candidate can find the longest prefix of $t$ that already exists as a subsequence in $s$.

Algorithmic pattern used

This problem is solved using the Two Pointers and Greedy patterns.

1. Pointer 1: Start at the beginning of string $s$.
2. Pointer 2: Start at the beginning of string $t$.
3. Traversal: Iterate through $s$. Whenever the character at s[p1] matches the character at t[p2], increment p2. Always increment p1.
4. Conclusion: After traversing $s$, the value of p2 tells you how many characters of $t$ are already present as a subsequence. The number of characters to append is the remaining length of $t$: length(t) - p2.

Example explanation

String $s$: "abcde", String $t$: "acegh"

1. Pointer p2 at 'a'. Find 'a' in $s$. Match! p2 moves to 'c'.
2. Find 'c' in $s$. Match! p2 moves to 'e'.
3. Find 'e' in $s$. Match! p2 moves to 'g'.
4. Continue through $s$. No 'g' found.
5. p2 stops after matching 3 characters ("ace"). Length of $t$ is 5. Characters to append: $5 - 3 = 2$ (the "gh" part).

Common mistakes candidates make

• Confusing Subsequence with Substring: Trying to find a continuous block of characters instead of allowing gaps.
• Over-complicating with DP: Attempting a complex Dynamic Programming approach (like Longest Common Subsequence) when a simple linear scan is faster and sufficient.
• Wrong Append Location: Forgetting that characters can only be added to the end of $s$, which simplifies the problem significantly.

Interview preparation tip

Whenever a problem involves "subsequences" and "minimum characters," first check if a greedy approach with two pointers works. It's almost always $O(N)$ and much more efficient than DP.