Start by checking how much of t is already a subsequence of s using a two-pointer approach. Track the longest prefix of t matching s and calculate the remaining characters to append. This ensures a minimal append count and avoids unnecessary operations, directly applying the two-pointer scanning with invariant tracking pattern for optimal efficiency.
Problem Statement
Given two strings s and t containing only lowercase English letters, determine how many characters must be appended to the end of s so that t becomes a subsequence of s. You must preserve the order of characters in t when making it a subsequence.
Return the minimum number of characters that need to be added. A subsequence is formed by deleting zero or more characters from s without changing the order of the remaining characters, ensuring t appears sequentially in the modified string.
Examples
Example 1
Input: s = "coaching", t = "coding"
Output: 4
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
t is already a subsequence of s ("abcde").
Example 3
Input: s = "z", t = "abcde"
Output: 5
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 <= 105
- s and t consist only of lowercase English letters.
Solution Approach
Two-Pointer Prefix Matching
Initialize two pointers, one for s and one for t. Move through s and advance the t pointer when characters match, tracking the longest prefix of t that is a subsequence of s. The remaining characters of t after the last matched prefix indicate how many must be appended.
Greedy Append Calculation
Once the maximum prefix of t matching s is identified, calculate the difference between t's length and the matched prefix length. Append exactly this number of characters to s to guarantee t becomes a subsequence without over-appending.
Invariant Tracking Optimization
Maintain the invariant that the t pointer never moves backward. This ensures linear scanning of s and constant space usage, avoiding repeated rescanning or backtracking, which aligns with the problem's two-pointer scanning with invariant tracking pattern.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Time complexity is O(n) since each character in s and t is visited at most once. Space complexity is O(1) because only pointers and counters are used, without additional data structures.
What Interviewers Usually Probe
- Asks about matching t's prefix efficiently within s using minimal extra characters.
- Hints at using two pointers to avoid nested loops or repeated scans.
- Checks understanding of subsequence invariants and linear time guarantees.
Common Pitfalls or Variants
Common pitfalls
- Attempting to check subsequences by generating all combinations of s and t, which is too slow.
- Resetting the t pointer incorrectly when a match fails, breaking the invariant.
- Over-appending characters without calculating the longest prefix of t already present in s.
Follow-up variants
- Count minimal characters to prepend instead of append to make t a subsequence.
- Modify s in-place with limited extra memory to achieve the subsequence.
- Determine the minimum number of deletions from s to make t a subsequence.
How GhostInterview Helps
- Provides step-by-step two-pointer guidance for prefix matching and append calculation.
- Highlights invariant tracking to avoid backtracking mistakes and ensure linear efficiency.
- Visualizes exactly which characters of t are missing from s to minimize appends and confirm correctness.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the core pattern for Append Characters to String to Make Subsequence?
The problem uses a two-pointer scanning with invariant tracking pattern, focusing on identifying the longest prefix of t already in s.
Can t be already a subsequence of s?
Yes, if the entire t matches sequentially within s, no characters need to be appended, so the result is zero.
How do you handle large strings efficiently?
Use two pointers to scan s and t linearly without extra data structures, maintaining constant space for counters and positions.
Is there a greedy approach in this problem?
Yes, after finding the maximal prefix of t in s, greedily append only the remaining unmatched characters to minimize operations.
What are common mistakes solving this problem?
Overcomplicating by generating subsequences, incorrectly moving pointers, or appending extra characters beyond the minimal required.
Need direct help with Append Characters to String to Make Subsequence instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Append Characters to String to Make Subsequence from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the maximum number of non-overlapping palindromic substrings of at least length k in a string using dynamic programming.
Open problem page#2697 Lexicographically Smallest PalindromeGiven a string, make it a palindrome with the fewest operations, prioritizing lexicographically smallest result.
Open problem page#2193 Minimum Number of Moves to Make PalindromeThe problem challenges you to find the minimum number of adjacent swaps to make a string a palindrome.
Open problem page