Append Characters to String to Make Subsequence

How it works

The two-pointer approach scans s character by character, which can be slow if s is long and the characters we need are sparse. We can speed this up by precomputing where each character appears in s. For any position, we can instantly jump to the next occurrence of the character we need.

We build a table where store[i][c] tells us the nearest index at or after position i where character c appears. This lets us skip over irrelevant characters in constant time.

Steps

1. Build a 2D array store where store[i][c] holds the first occurrence of character c at or after index i in s.
2. Fill this table by iterating backward through s. Each position inherits the next position's data, then updates the current character's entry.
3. Use two pointers i and j for s and t. For each character in t, use store to jump directly to its next occurrence in s.
4. If a character from t cannot be found (returns sentinel value), stop matching.
5. Return len(t) - j.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(n)

Where n and m are the lengths of the strings s and t, respectively.

Things to watch for

Returning the Wrong Value After Matching

The result should be the number of unmatched characters in t, not the number of matched characters. After the loop, j represents how many characters were matched, so you need to return len(t) - j, not j.

Advancing Both Pointers on Mismatch

When characters do not match, only the pointer for s should advance. The pointer for t should stay in place waiting for its character to appear later in s. Advancing both pointers skips characters in t that might match later.

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        store = [[n + 1] * 26 for _ in range(n)]
        store[n - 1][ord(s[n - 1]) - ord('a')] = n - 1

        for i in range(n - 2, -1, -1):
            store[i] = store[i + 1][:]
            store[i][ord(s[i]) - ord('a')] = i

        i, j = 0, 0
        while i < n and j < m:
            if store[i][ord(t[j]) - ord('a')] == n + 1:
                break

            i = store[i][ord(t[j]) - ord('a')] + 1
            j += 1

        return m - j

class Solution {
public:
    int appendCharacters(string s, string t) {
        int n = s.length(), m = t.length();
        vector<vector<int>> store(n, vector<int>(26, n + 1));
        store[n - 1][s[n - 1] - 'a'] = n - 1;

        for (int i = n - 2; i >= 0; i--) {
            store[i] = store[i + 1];
            store[i][s[i] - 'a'] = i;
        }

        int i = 0, j = 0;
        while (i < n && j < m) {
            if (store[i][t[j] - 'a'] == n + 1) {
                break;
            }
            i = store[i][t[j] - 'a'] + 1;
            j++;
        }

        return m - j;
    }
};