⚡Flashcard Drill➔
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

  1. Appending characters can only extend s at the end, so the already-matched prefix of t is fixed.
  2. Find the longest prefix of t that is already a subsequence of s -- exactly the two-pointer scan from Is Subsequence.
  3. The unmatched suffix of t must be appended verbatim, so the answer is len(t) - matched.
  4. 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 t greedily from the end: the appended characters go at the end of s, so the matched prefix must be as long as possible from the front.
  • Returning len(t) unconditionally: if t is already a subsequence, the answer is 0.
  • Re-scanning s for each character of t: 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems