Tap here to switch tabs

Problem

Ask

Submissions

Home

Courses

Grokking the Coding Interview Patterns

Problem: Append Characters to String to Make Subsequence

med

30 min

Explore how to determine the minimum characters to append to a source string to make a target string its subsequence. Learn to apply two-pointer techniques efficiently for solving linear string problems while understanding subsequence concepts and constraints.

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.

Examples

1 / 6

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Append Characters to String to Make Subsequence

Given source = "axbyc" and target = "abcde".

What is the minimum number of characters to append so the target becomes a subsequence?

$1$

$3$

$2$

$4$

1 / 4

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding on how to solve this problem.

Sequence - Vertical

Drag and drop the cards to rearrange them in the correct sequence.

Try it yourself

Implement your solution in the following coding playground.

⋮