Is Append Characters to String to Make Subsequence easy or hard?

The problem is rated Medium on LeetCode but behaves like an easier greedy pattern once you recognize the subsequence scan. The challenge is identifying that a simple two-pointer pass is sufficient instead of using dynamic programming.

Append Characters to String to Make Subsequence Python/Java solution

Most implementations use the same two-pointer logic across languages. Iterate through s, advance the pointer in t when characters match, and return the remaining length of t. The code is straightforward in Python, Java, C++, JavaScript, and C# with O(n + m) runtime.

How to solve Append Characters to String to Make Subsequence in O(n)?

Use two pointers to scan both strings. Iterate through s and advance a second pointer whenever the current character matches the next needed character in t. When the scan finishes, the unmatched portion of t represents the characters that must be appended. The total complexity is O(n + m).

What is the best approach for Append Characters to String to Make Subsequence?

The optimal solution uses a greedy two-pointer technique. One pointer scans string s while another tracks progress through t. Each time characters match, advance the pointer in t. After scanning s, the number of remaining characters in t is the minimum you must append. This runs in O(n + m) time with O(1) space.

Is Append Characters to String to Make Subsequence asked at Google/Amazon/Meta?

Subsequence and two-pointer problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involving subsequence matching, greedy scanning, and string processing are common screening questions.

What data structure is used in Append Characters to String to Make Subsequence?

The optimal solution does not require complex data structures. It relies on two pointers and simple string traversal. The dynamic programming variant uses a 2D DP table to compute the longest common subsequence.

What is the time complexity of Append Characters to String to Make Subsequence?

The optimal two-pointer solution runs in O(n + m) time, where n is the length of s and m is the length of t. Each character from both strings is processed at most once. Space complexity is O(1) since only a few pointer variables are used.

Description Hints 3 Solution Video 7:04

2486. Append Characters to String to Make Subsequence

Medium72.9% acceptance2 companies

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

Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of 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.

Example 1:

Input: s = "coaching", t = "coding"
Output: 4
Explanation: Append the characters "ding" to the end of s so that s = "coachingding".
Now, t is a subsequence of s ("coachingding").
It can be shown that appending any 3 characters to the end of s will never make t a subsequence.

Example 2:

Input: s = "abcde", t = "a"
Output: 0
Explanation: t is already a subsequence of s ("abcde").

Example 3:

Input: s = "z", t = "abcde"
Output: 5
Explanation: Append the characters "abcde" to the end of s so that s = "zabcde".
Now, t is a subsequence of s ("zabcde").
It can be shown that appending any 4 characters to the end of s will never make t a subsequence.

Constraints:

1 <= s.length, t.length <= 10⁵
s and t consist only of lowercase English letters.

Asked at 2 companies

Amazon

Google

Topics

Hints open one at a time

Hint 1

Find the longest prefix of t that is a subsequence of s.

Hint 2

Use two variables to keep track of your location in s and t. If the characters match, increment both variables. Otherwise, only increment the variable for s.

Hint 3

The remaining characters in t must be appended to the end of s.

7:04

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution