#2486

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Append Characters to String to Make Subsequence

Name: Interview AiBox
Availability: InStock
Rating: 4.9 (10000 reviews)

Determine the minimum characters to append to s so t becomes a subsequence using efficient two-pointer scanning techniques.

two pointers string greedy

Problem Statement

Given two strings s and t containing only lowercase English letters, determine how many characters must be appended to the end of s so that t becomes a subsequence of s. You must preserve the order of characters in t when making it a subsequence.

Return the minimum number of characters that need to be added. A subsequence is formed by deleting zero or more characters from s without changing the order of the remaining characters, ensuring t appears sequentially in the modified string.

Examples

Example 1

Input: s = "coaching", t = "coding"

Output: 4

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

t is already a subsequence of s ("abcde").

Example 3

Input: s = "z", t = "abcde"

Output: 5

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 <= 105
s and t consist only of lowercase English letters.

Solution Approach

Two-Pointer Prefix Matching

Initialize two pointers, one for s and one for t. Move through s and advance the t pointer when characters match, tracking the longest prefix of t that is a subsequence of s. The remaining characters of t after the last matched prefix indicate how many must be appended.

Greedy Append Calculation

Once the maximum prefix of t matching s is identified, calculate the difference between t's length and the matched prefix length. Append exactly this number of characters to s to guarantee t becomes a subsequence without over-appending.

Invariant Tracking Optimization

Maintain the invariant that the t pointer never moves backward. This ensures linear scanning of s and constant space usage, avoiding repeated rescanning or backtracking, which aligns with the problem's two-pointer scanning with invariant tracking pattern.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) since each character in s and t is visited at most once. Space complexity is O(1) because only pointers and counters are used, without additional data structures.

What Interviewers Usually Probe

Asks about matching t's prefix efficiently within s using minimal extra characters.
Hints at using two pointers to avoid nested loops or repeated scans.
Checks understanding of subsequence invariants and linear time guarantees.

Common Pitfalls or Variants

Common pitfalls

Attempting to check subsequences by generating all combinations of s and t, which is too slow.
Resetting the t pointer incorrectly when a match fails, breaking the invariant.
Over-appending characters without calculating the longest prefix of t already present in s.

Follow-up variants

Count minimal characters to prepend instead of append to make t a subsequence.
Modify s in-place with limited extra memory to achieve the subsequence.
Determine the minimum number of deletions from s to make t a subsequence.

FAQ

What is the core pattern for Append Characters to String to Make Subsequence?

The problem uses a two-pointer scanning with invariant tracking pattern, focusing on identifying the longest prefix of t already in s.

Can t be already a subsequence of s?

Yes, if the entire t matches sequentially within s, no characters need to be appended, so the result is zero.

How do you handle large strings efficiently?

Use two pointers to scan s and t linearly without extra data structures, maintaining constant space for counters and positions.

Is there a greedy approach in this problem?

Yes, after finding the maximal prefix of t in s, greedily append only the remaining unmatched characters to minimize operations.

What are common mistakes solving this problem?

Overcomplicating by generating subsequences, incorrectly moving pointers, or appending extra characters beyond the minimal required.

terminal

Solution

Solution 1: Two Pointers

We define two pointers $i$ and $j$, pointing to the first characters of strings $s$ and $t$ respectively. We iterate through string $s$, if $s[i] = t[j]$, then we move $j$ one step forward. Finally, we return $n - j$, where $n$ is the length of string $t$.

1

2

3

4

5

6

7

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        n, j = len(t), 0
        for c in s:
            if j < n and c == t[j]:
                j += 1
        return n - j

Continue Practicing

#2472 maximum number of non overlapping palindrome substrings #2697 lexicographically smallest palindrome #2193 minimum number of moves to make palindrome