Append Characters to String to Make Subsequence - Solution & Explanation
Problem Statement
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 <= 105sandtconsist only of lowercase English letters.
Approach Overview
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 1: Two-Pointer Approach
This approach uses two pointers to scan both strings, one pointer for each string. The idea is to attempt to match characters of t with those in s. A character from t is successfully matched if it is equal to the current character in s. We iterate through s, moving the pointer for each character matched, while the pointer for t only moves if a match is found. Once we've iterated through s, we determine how many characters are left unmatched in t, which is the number of characters needed to be appended to s.
The C solution declares a function minCharsToAppend that takes two strings, s and t, and calculates the minimum number of characters required to append to s to make t a subsequence. We use two indices to traverse the strings, incrementing sIndex for each iteration and only incrementing tIndex when characters match. Finally, we calculate the number of unmatched characters in t and return it.
Complexity
Time Complexity: O(n + m) where n is the length of s and m is the length of t.
Space Complexity: O(1) as no additional space is used.
Approach 2: Dynamic Programming Approach
This approach uses dynamic programming to precompute the next occurrence of each character for every position in the string s. By doing so, we quickly identify the existence and location of each character from t in s. We build a 2D array next where next[i][j] represents the smallest index >= i that holds the character j in s. This helps in efficiently determining the position of characters and the necessary additions to the end of the string.
buildNext function precomputes the next occurrences of each character for every index. Using this information, we find out how to move through s to match t and calculate how many characters in t are not matched, hence needing to be appended.
Complexity
Time Complexity: O(n + m + n * ALPHABET_SIZE) due to preprocessing each character for positions.
Space Complexity: O(n * ALPHABET_SIZE) used by the 2D array next where n is length of s.
Approach 3: Two Pointers
We define two pointers i and j, pointing to the first characters of strings s and t respectively. We iterate through string s, if s[i] = t[j], then we move j one step forward. Finally, we return n - j, where n is the length of string t.
The time complexity is O(m + n), where m and n are the lengths of strings s and t respectively. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n + m) where n is the length of |
| Dynamic Programming Approach | Time Complexity: O(n + m + n * ALPHABET_SIZE) due to preprocessing each character for positions. |
| Two Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Append Characters to Strings to Make Subsequence - Leetcode 2486 - Python • NeetCodeIO • 8,863 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Append Characters to String to Make Subsequence easy or hard?
Append Characters to String to Make Subsequence Python/Java solution
How to solve Append Characters to String to Make Subsequence in O(n)?
What is the best approach for Append Characters to String to Make Subsequence?
Is Append Characters to String to Make Subsequence asked at Google/Amazon/Meta?
What data structure is used in Append Characters to String to Make Subsequence?
What is the time complexity of Append Characters to String to Make Subsequence?
Ready to solve this problem?
Practice Append Characters to String to Make Subsequence with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor