NeetCode #6LC-2486MediumArrays & Hashing
← Back to All Problems#6 · #2486 · Append Characters to String to Make Subsequence(追加字符以获得子序列)
📌 Problem Statement & Constraints
Given strings
s and t, return the minimum number of characters that must be appended to s so that t becomes a subsequence of s. Constraints: 1 <= s.length, t.length <= 10^5; both consist of lowercase English letters.💡 Core Algorithmic Approaches
- Appending characters can only extend
sat the end, so the already-matched prefix oftis fixed. - Find the longest prefix of
tthat is already a subsequence ofs-- exactly the two-pointer scan from Is Subsequence. - The unmatched suffix of
tmust be appended verbatim, so the answer islen(t) - matched. - There is no benefit to matching a later character while skipping an earlier one, because the appended characters preserve order.
💻 Benchmark Python3 Implementation
class Solution:
def appendCharacters(self, s: str, t: str) -> int:
i = 0 # pointer into t
for ch in s:
if i < len(t) and ch == t[i]:
i += 1 # matched one more character of t
if i == len(t):
break
return len(t) - i # append the unmatched suffix⚡ Complexity Deep Dive
⏱️ Time Complexity
O(|s|): one pass over s, stopping early once t is fully matched.
💾 Space Complexity
O(1): two counters.
⚠️ Interview Pitfalls & Follow-ups
- Trying to match
tgreedily from the end: the appended characters go at the end ofs, so the matched prefix must be as long as possible from the front. - Returning
len(t)unconditionally: iftis already a subsequence, the answer is 0. - Re-scanning
sfor each character oft: O(|s| * |t|) instead of a single linear pass.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.