Problem Description

You are given two strings s and t consisting of only lowercase English letters.

Your task is to determine the minimum number of characters that need to be appended to the end of string s so that string t becomes a subsequence of the modified string 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. For example, "ace" is a subsequence of "abcde" because you can delete 'b' and 'd' to get "ace" while maintaining the relative order.

The solution uses a two-pointer approach. We traverse through string s with one pointer and try to match as many characters as possible from string t using another pointer j. Whenever we find a matching character s[i] == t[j], we advance the pointer j in string t. After traversing the entire string s, the pointer j tells us how many characters from t we've successfully matched as a subsequence. The remaining unmatched characters (n - j) need to be appended to s to make t a complete subsequence.

For example:

• If s = "coaching" and t = "coding", we can match "co", "di", "n", "g" from s in order, which gives us "coing". We still need to append "d" to make "coding" a subsequence, so the answer is 1.
• If s = "abcde" and t = "a", the entire t is already a subsequence of s, so we need to append 0 characters.

Intuition

The key insight is that we want to find the longest prefix of t that already exists as a subsequence in s. Whatever portion of t we can already find in s doesn't need to be appended - we only need to append the remaining suffix of t.

Think of it this way: if we scan through s from left to right and try to match characters from t in order, we're essentially finding how much of t is already "hidden" within s as a subsequence. The characters we successfully match don't need to be added again.

For example, if s = "abc" and t = "abcd", we can match "a", "b", "c" from t within s. Only the "d" is missing, so we just need to append "d".

This naturally leads to a greedy approach: as we traverse s, whenever we see a character that matches the current character we're looking for in t, we take it. We can't do better by skipping a matching character and hoping to find it later, because:

1. We're only allowed to append at the end of s
2. The order of characters in the subsequence must be preserved
3. Using an earlier occurrence of a character gives us more opportunities to match subsequent characters

By greedily matching characters from the beginning of t as we scan through s, we maximize the number of characters from t that are already present as a subsequence. The remaining unmatched portion of t represents the minimum characters we must append.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

The solution implements a two-pointer technique to efficiently find how many characters from string t are already present as a subsequence in string s.

Algorithm Steps:

1. Initialize a pointer j = 0 to track our current position in string t, and store the length of t in variable n.

2. Iterate through each character c in string s:

   • Check if we haven't finished matching all characters of t (i.e., j < n)
   • If the current character c matches the character at position j in string t (i.e., c == t[j]), increment j by 1
   • This means we've successfully found one more character from t in the correct order

3. After traversing the entire string s, the pointer j indicates how many characters from t we've successfully matched as a subsequence in s.

4. Return n - j, which represents the number of remaining characters from t that need to be appended to s.

Why this works:

• The variable j acts as a progress tracker for string t
• As we scan through s, we only advance j when we find a matching character
• Since we process s from left to right and only move forward in t, we maintain the subsequence property
• Characters at positions [0, j-1] in t have been matched, while characters at positions [j, n-1] still need to be appended

Time Complexity: O(m) where m is the length of string s, as we traverse s once.

Space Complexity: O(1) as we only use a constant amount of extra space for the pointer and length variable.

Example Walkthrough

Let's walk through the solution with s = "coaching" and t = "coding".

Initial Setup:

• String s = "coaching" (length 8)
• String t = "coding" (length 6)
• Initialize pointer j = 0 (pointing to 'c' in t)
• Store n = 6 (length of t)

Step-by-step traversal of s:

1. i=0, s[0]='c': Compare with t[0]='c'

   • Match found! Increment j to 1
   • Progress: matched "c" from t

2. i=1, s[1]='o': Compare with t[1]='o'

   • Match found! Increment j to 2
   • Progress: matched "co" from t

3. i=2, s[2]='a': Compare with t[2]='d'

   • No match, j stays at 2
   • Still looking for 'd' from t

4. i=3, s[3]='c': Compare with t[2]='d'

   • No match, j stays at 2
   • Still looking for 'd' from t

5. i=4, s[4]='h': Compare with t[2]='d'

   • No match, j stays at 2
   • Still looking for 'd' from t

6. i=5, s[5]='i': Compare with t[2]='d'

   • No match, j stays at 2
   • Still looking for 'd' from t

7. i=6, s[6]='n': Compare with t[2]='d'

   • No match, j stays at 2
   • Still looking for 'd' from t

8. i=7, s[7]='g': Compare with t[2]='d'

   • No match, j stays at 2
   • Still looking for 'd' from t

Final Calculation:

• After traversing all of s, j = 2
• We matched 2 characters from t ("co")
• Characters to append = n - j = 6 - 2 = 4
• We need to append "ding" to make "coding" a subsequence

Result: Return 4

Note: This example shows that we only matched the first two characters "co" from "coding" in the string "coaching". The remaining characters "ding" need to be appended.

Solution Implementation

Time and Space Complexity

The time complexity is O(m), where m is the length of string s. The algorithm iterates through each character in string s exactly once using a single for loop. Although we also access characters from string t, we only do so when there's a match, and the pointer j moves at most n times (where n is the length of t). Since we traverse string s completely, the dominant factor is O(m).

The space complexity is O(1). The algorithm only uses a constant amount of extra space: two integer variables n and j to store the length of string t and track the current position in t respectively. No additional data structures that grow with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Match Characters Out of Order

A common mistake is trying to find ALL characters of t in s without considering the order constraint. Some might incorrectly count character frequencies or use a set-based approach.

Incorrect Approach:

def appendCharacters(self, s: str, t: str) -> int:
    # WRONG: This counts frequencies, ignoring order
    s_chars = set(s)
    count = 0
    for char in t:
        if char in s_chars:
            count += 1
    return len(t) - count

Why it fails: For s = "abc" and t = "abac", this would incorrectly return 0 (thinking all characters exist), but the correct answer is 2 because we need the second 'a' and 'c' in proper sequence.

2. Resetting or Backtracking the Source String Pointer

Some might think they need to restart scanning s when they find a match or implement backtracking logic.

Incorrect Approach:

def appendCharacters(self, s: str, t: str) -> int:
    # WRONG: Unnecessarily complex with potential to revisit characters
    for j in range(len(t)):
        found = False
        for i in range(len(s)):  # Restarting from beginning each time
            if s[i] == t[j]:
                found = True
                s = s[i+1:]  # Modifying string (inefficient)
                break
        if not found:
            return len(t) - j
    return 0

Why it fails: This is inefficient and overly complex. The beauty of the two-pointer approach is its single-pass nature.

3. Forgetting Edge Cases

Not handling cases where one or both strings are empty, or where t is longer than s.

Solution to avoid pitfalls:

def appendCharacters(self, s: str, t: str) -> int:
    # Handle edge cases explicitly (though the main algorithm handles them correctly)
    if not t:  # Empty target string
        return 0
    if not s:  # Empty source string
        return len(t)
  
    # Standard two-pointer approach
    j = 0
    for char in s:
        if j < len(t) and char == t[j]:
            j += 1
  
    return len(t) - j

4. Misunderstanding the Problem Statement

Some might think they need to find the longest common subsequence (LCS) or that they can rearrange characters.

Key clarifications:

• Characters must be appended only at the END of s
• The order of characters in both strings must be preserved
• We're looking for t as a subsequence, not a substring
• We cannot insert characters in the middle or rearrange existing characters

The correct solution's simplicity lies in understanding that we only need to track progress through t while scanning s once, making it both intuitive and efficient.