Watch 10 video solutions for Append Characters to String to Make Subsequence, a medium level problem involving Two Pointers, String, Greedy. This walkthrough by NeetCodeIO has 8,293 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: s = "coaching", t = "coding"
Output: 4
Explanation: Append the characters "ding" to the end of s so that s = "coachingding".
Now, t is a subsequence of s ("coachingding").
It can be shown that appending any 3 characters to the end of s will never make t a subsequence.
Example 2:
Input: s = "abcde", t = "a"
Output: 0
Explanation: t is already a subsequence of s ("abcde").
Example 3:
Input: s = "z", t = "abcde"
Output: 5
Explanation: Append the characters "abcde" to the end of s so that s = "zabcde".
Now, t is a subsequence of s ("zabcde").
It can be shown that appending any 4 characters to the end of s will never make t a subsequence.
Constraints:
1 <= s.length, t.length <= 105s and t consist only of lowercase English letters.Problem Overview: Given two strings s and t, determine the minimum number of characters you must append to the end of s so that t becomes a subsequence of s. A subsequence means characters appear in order but not necessarily contiguously.
Approach 1: Two-Pointer Greedy (O(n + m) time, O(1) space)
This approach scans both strings using two pointers. One pointer iterates through s, while the other tracks how many characters of t have been matched so far. Every time characters match, advance the pointer in t. By the time you finish scanning s, the pointer position in t tells you how many characters were successfully matched. The remaining suffix of t must be appended to s. The greedy insight is simple: always match characters as early as possible while scanning left to right. Because each string is traversed once, the runtime is linear. This pattern appears frequently in problems involving subsequences and is a standard use of two pointers with greedy matching.
Approach 2: Dynamic Programming (O(n × m) time, O(n × m) space)
A more general method treats the problem as a longest common subsequence (LCS) variant. Build a DP table where dp[i][j] represents the length of the longest subsequence match between the first i characters of s and the first j characters of t. If characters match, extend the subsequence; otherwise carry forward the best result from adjacent states. Once the table is filled, the LCS length tells you how many characters of t already appear in order within s. The answer becomes m - LCS, where m is the length of t. This approach is more flexible for generalized subsequence problems but is significantly slower and uses more memory. It mainly serves as a conceptual baseline for understanding subsequence matching using string DP.
Recommended for interviews: The two-pointer greedy solution is what interviewers expect. It demonstrates that you recognize the subsequence pattern and can implement an optimal linear scan. Mentioning the DP/LCS formulation shows deeper understanding, but writing the O(n + m) greedy solution proves you can optimize beyond the brute-force or quadratic approaches.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Greedy | O(n + m) | O(1) | Best choice for subsequence matching when only order matters |
| Dynamic Programming (LCS) | O(n × m) | O(n × m) | Useful when extending the problem to general subsequence comparisons |