Solution: Append Characters to String to Make Subsequence

Statement▼

You’re given two strings, source and target, made up of lowercase English letters. Your task is to determine the minimum number of characters that must be appended to the end of the source so that the target becomes a subsequence of the resulting string.

Note: A subsequence is formed by deleting zero or more characters from a string without changing the order of the remaining characters.

Constraints:

$1 \leq$ source.length, target.length $\leq 10^3$
source and target consist only of lowercase English letters.

The goal is to determine the minimum number of characters that must be appended to a given source string so that the target string becomes a subsequence. Instead of transforming or inserting arbitrary characters, we aim to append the fewest possible characters to the source string.

A small intuition example:

If source = "abcccb" and target = "cccbaaa", we only need to append "aaa" from target, not the whole string. Appending "aaa" makes the source string "abcccbaaa", where the last seven characters now act as a subsequence matching the entire target.

The algorithm will use a greedy two pointer approach to identify how much of the target is already present in order within the source. It iterates through both strings using:

A pointer, source_index, on the source that moves forward at every step.
A pointer, target_index, on the target that moves forward only when a match is found.

By the end of the loop, the target_index pointer indicates how many characters have been matched. The remaining characters (target_length - target_index) must be appended to the end of the source.

This greedy two pointers strategy ensures we match characters as early as possible, avoiding unnecessary additions. Even if appending more characters could work, we only append what is required to complete the subsequence.

Using the intuition above, we implement the algorithm as follows:

We create two pointers, source_index and target_index, initialized to 0.
We also store the lengths of the strings in source_length and target_length.
Iterate until source_index is less than the source_length and target_index is less than the target_length:
1. If during the iteration, source[source_index] becomes equal to target[target_index]:
  1. We increment target_index to use the next character of the target.
2. Next, we increment source_index to continue scanning the source string.
Once the loop breaks, we return the result calculated as the difference between target_length and target_index.

Let’s look at the following illustration to get a better understanding of the solution:

⋮

Problem

Submissions