2486. Append Characters to Make Subsequence

The problem

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.

Approach overview

Problem Overview: Given two strings s and t, determine the minimum number of characters you must append to the end of s so that t becomes a subsequence of s. A subsequence means characters appear in order but not necessarily contiguously.

Approach 1: Two-Pointer Greedy (O(n + m) time, O(1) space)

This approach scans both strings using two pointers. One pointer iterates through s, while the other tracks how many characters of t have been matched so far. Every time characters match, advance the pointer in t. By the time you finish scanning s, the pointer position in t tells you how many characters were successfully matched. The remaining suffix of t must be appended to s. The greedy insight is simple: always match characters as early as possible while scanning left to right. Because each string is traversed once, the runtime is linear. This pattern appears frequently in problems involving subsequences and is a standard use of two pointers with greedy matching.

Approach 2: Dynamic Programming (O(n × m) time, O(n × m) space)

A more general method treats the problem as a longest common subsequence (LCS) variant. Build a DP table where dp[i][j] represents the length of the longest subsequence match between the first i characters of s and the first j characters of t. If characters match, extend the subsequence; otherwise carry forward the best result from adjacent states. Once the table is filled, the LCS length tells you how many characters of t already appear in order within s. The answer becomes m - LCS, where m is the length of t. This approach is more flexible for generalized subsequence problems but is significantly slower and uses more memory. It mainly serves as a conceptual baseline for understanding subsequence matching using string DP.

Recommended for interviews: The two-pointer greedy solution is what interviewers expect. It demonstrates that you recognize the subsequence pattern and can implement an optimal linear scan. Mentioning the DP/LCS formulation shows deeper understanding, but writing the O(n + m) greedy solution proves you can optimize beyond the brute-force or quadratic approaches.

Approach 1: Two-Pointer Approach

This approach uses two pointers to scan both strings, one pointer for each string. The idea is to attempt to match characters of t with those in s. A character from t is successfully matched if it is equal to the current character in s. We iterate through s, moving the pointer for each character matched, while the pointer for t only moves if a match is found. Once we've iterated through s, we determine how many characters are left unmatched in t, which is the number of characters needed to be appended to s.

Python

def minCharsToAppend(s, t):
    s_len, t_len = len(s), len(t)
    s_index, t_index = 0, 0

    while s_index < s_len and t_index < t_len:
        if s[s_index] == t[t_index]:
            t_index += 1
        s_index += 1

    return t_len - t_index

# Testing the function
s = "coaching"
t = "coding"
print(minCharsToAppend(s, t))

Java

public class MinCharsAppend {
    public static int minCharsToAppend(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        int sIndex = 0, tIndex = 0;

        while (sIndex < sLen && tIndex < tLen) {
            if (s.charAt(sIndex) == t.charAt(tIndex)) {
                tIndex++;
            }
            sIndex++;
        }

        return tLen - tIndex;
    }

    public static void main(String[] args) {
        String s = "coaching";
        String t = "coding";
        System.out.println(minCharsToAppend(s, t));
    }
}

C++

#include <iostream>
#include <string>

int minCharsToAppend(const std::string& s, const std::string& t) {
    int sLen = s.length();
    int tLen = t.length();
    int sIndex = 0, tIndex = 0;

    while (sIndex < sLen && tIndex < tLen) {
        if (s[sIndex] == t[tIndex]) {
            tIndex++;
        }
        sIndex++;
    }

    return tLen - tIndex;
}

int main() {
    std::string s = "coaching";
    std::string t = "coding";
    std::cout << minCharsToAppend(s, t) << std::endl;
    return 0;
}

JavaScript

function minCharsToAppend(s, t) {
    let sLen = s.length;
    let tLen = t.length;
    let sIndex = 0, tIndex = 0;

    while (sIndex < sLen && tIndex < tLen) {
        if (s[sIndex] === t[tIndex]) {
            tIndex++;
        }
        sIndex++;
    }

    return tLen - tIndex;
}

// Testing the function
let s = "coaching";
let t = "coding";
console.log(minCharsToAppend(s, t));

#include <stdio.h>
#include <string.h>

int minCharsToAppend(char* s, char* t) {
    int sLen = strlen(s);
    int tLen = strlen(t);
    int sIndex = 0, tIndex = 0;

    while (sIndex < sLen && tIndex < tLen) {
        if (s[sIndex] == t[tIndex]) {
            tIndex++;
        }
        sIndex++;
    }

    return tLen - tIndex;
}

int main() {
    char s[] = "coaching";
    char t[] = "coding";
    printf("%d\n", minCharsToAppend(s, t));
    return 0;
}

using System;

public class MinChars
{
    public static int MinCharsToAppend(string s, string t)
    {
        int sLen = s.Length;
        int tLen = t.Length;
        int sIndex = 0, tIndex = 0;

        while (sIndex < sLen && tIndex < tLen)
        {
            if (s[sIndex] == t[tIndex])
            {
                tIndex++;
            }
            sIndex++;
        }

        return tLen - tIndex;
    }

    public static void Main()
    {
        string s = "coaching";
        string t = "coding";
        Console.WriteLine(MinCharsToAppend(s, t));
    }
}

The Python solution defines the function minCharsToAppend where two indices are used to iterate over the strings. For every matched character, the index of t moves forward. The number of unmatched characters in t is returned as the count of characters to append.

Complexity

Time Complexity: O(n + m) where n is the length of s and m is the length of t.
Space Complexity: O(1) due to minimal space usage.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

This approach uses dynamic programming to precompute the next occurrence of each character for every position in the string s. By doing so, we quickly identify the existence and location of each character from t in s. We build a 2D array next where next[i][j] represents the smallest index >= i that holds the character j in s. This helps in efficiently determining the position of characters and the necessary additions to the end of the string.

Python

def minCharsToAppend(s, t):
    s_len, t_len = len(s), len(t)
    next_pos = [[s_len] * 26 for _ in range(s_len + 1)]

    last = [s_len] * 26
    for i in range(s_len - 1, -1, -1):
        last[ord(s[i]) - ord('a')] = i
        for j in range(26):
            next_pos[i][j] = last[j]

    pos = 0
    append_count = 0
    for c in t:
        if next_pos[pos][ord(c) - ord('a')] == s_len:
            append_count += (t_len - t.index(c))
            break
        pos = next_pos[pos][ord(c) - ord('a')] + 1

    return append_count

# Testing the function
s = "coaching"
t = "coding"
print(minCharsToAppend(s, t))

Java

import java.util.Arrays;

public class MinCharsAppend {
    public static int minCharsToAppend(String s, String t) {
        int sLen = s.length(), tLen = t.length();
        int[][] next = new int[sLen + 1][26];

        for (int[] row : next) {
            Arrays.fill(row, sLen);
        }

        int[] last = new int[26];
        Arrays.fill(last, sLen);

        for (int i = sLen - 1; i >= 0; i--) {
            last[s.charAt(i) - 'a'] = i;
            System.arraycopy(last, 0, next[i], 0, 26);
        }

        int pos = 0, appendCount = 0;
        for (int i = 0; i < tLen; i++) {
            if (next[pos][t.charAt(i) - 'a'] == sLen) {
                appendCount += (tLen - i);
                break;
            }
            pos = next[pos][t.charAt(i) - 'a'] + 1;
        }

        return appendCount;
    }

    public static void main(String[] args) {
        String s = "coaching";
        String t = "coding";
        System.out.println(minCharsToAppend(s, t));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void buildNext(const string &s, vector<vector<int>> &next) {
    int sLen = s.length();
    vector<int> last(26, sLen);
    for (int i = sLen - 1; i >= 0; --i) {
        last[s[i] - 'a'] = i;
        for (int j = 0; j < 26; ++j) {
            next[i][j] = last[j];
        }
    }
}

int minCharsToAppend(const string &s, const string &t) {
    int sLen = s.length();
    int tLen = t.length();
    vector<vector<int>> next(sLen + 1, vector<int>(26, sLen));
    buildNext(s, next);
    int pos = 0, appendCount = 0;
    for (int i = 0; i < tLen; ++i) {
        if (next[pos][t[i] - 'a'] == sLen) {
            appendCount += (tLen - i);
            break;
        }
        pos = next[pos][t[i] - 'a'] + 1;
    }
    return appendCount;
}

int main() {
    string s = "coaching";
    string t = "coding";
    cout << minCharsToAppend(s, t) << endl;
    return 0;
}

JavaScript

function minCharsToAppend(s, t) {
    const sLen = s.length, tLen = t.length;
    const nextPos = Array.from({ length: sLen + 1 }, () => Array(26).fill(sLen));

    const last = Array(26).fill(sLen);
    for (let i = sLen - 1; i >= 0; i--) {
        last[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
        for (let j = 0; j < 26; j++) {
            nextPos[i][j] = last[j];
        }
    }

    let pos = 0, appendCount = 0;
    for (const char of t) {
        if (nextPos[pos][char.charCodeAt(0) - 'a'.charCodeAt(0)] === sLen) {
            appendCount += tLen - t.indexOf(char);
            break;
        }
        pos = nextPos[pos][char.charCodeAt(0) - 'a'.charCodeAt(0)] + 1;
    }

    return appendCount;
}

// Testing the function
let s = "coaching";
let t = "coding";
console.log(minCharsToAppend(s, t));

#include <stdio.h>
#include <string.h>

#define MAX_CHAR 26
#define MAX_LEN 100000

void buildNext(char *s, int next[][MAX_CHAR], int len) {
    int last[MAX_CHAR];
    for (int i = 0; i < MAX_CHAR; ++i) last[i] = len;
    for (int i = len - 1; i >= 0; --i) {
        last[s[i] - 'a'] = i;
        for (int j = 0; j < MAX_CHAR; ++j) {
            next[i][j] = last[j];
        }
    }
}

int minCharsToAppend(char *s, char *t) {
    int sLen = strlen(s);
    int tLen = strlen(t);
    int next[MAX_LEN + 1][MAX_CHAR];
    buildNext(s, next, sLen);
    int appendCount = 0, pos = 0;
    for (int i = 0; i < tLen; ++i) {
        if (next[pos][t[i] - 'a'] == sLen) {
            appendCount += (tLen - i);
            break;
        }
        pos = next[pos][t[i] - 'a'] + 1;
    }
    return appendCount;
}

int main() {
    char s[] = "coaching";
    char t[] = "coding";
    printf("%d\n", minCharsToAppend(s, t));
    return 0;
}

using System;

public class MinChars
{
    public static int MinCharsToAppend(string s, string t)
    {
        int sLen = s.Length;
        int tLen = t.Length;
        int[,] next = new int[sLen + 1, 26];

        for (int i = 0; i <= sLen; i++)
            for (int j = 0; j < 26; j++)
                next[i, j] = sLen;

        int[] last = new int[26];
        for (int i = 0; i < 26; i++) last[i] = sLen;

        for (int i = sLen - 1; i >= 0; i--) {
            last[s[i] - 'a'] = i;
            for (int j = 0; j < 26; j++)
                next[i, j] = last[j];
        }

        int pos = 0, appendCount = 0;
        for (int i = 0; i < tLen; i++) {
            if (next[pos, t[i] - 'a'] == sLen) {
                appendCount += (tLen - i);
                break;
            }
            pos = next[pos, t[i] - 'a'] + 1;
        }

        return appendCount;
    }

    public static void Main()
    {
        string s = "coaching";
        string t = "coding";
        Console.WriteLine(MinCharsToAppend(s, t));
    }
}

Python's solution defines the next_pos array, precomputing where each character appears next after each index and using this data to decide how many appended characters are necessary for t to be its subsequence.

Complexity

Time Complexity: O(n + m + n * ALPHABET_SIZE).
Space Complexity: O(n * ALPHABET_SIZE) due to storage in next_pos.

Try this approach in the editor

Approach 3: 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.

The time complexity is O(m + n), where m and n are the lengths of strings s and t respectively. The space complexity is O(1).

TypeScript

function appendCharacters(s: string, t: string): number {
    let j = 0;
    for (const c of s) {
        if (c === t[j]) {
            ++j;
        }
    }
    return t.length - j;
}

func appendCharacters(s string, t string) int {
	n, j := len(t), 0
	for _, c := range s {
		if j < n && byte(c) == t[j] {
			j++
		}
	}
	return n - j
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pointer Approach	Time Complexity: O(n + m) where n is the length of `s` and m is the length of `t`. Space Complexity: O(1) due to minimal space usage.
Dynamic Programming Approach	Time Complexity: O(n + m + n * ALPHABET_SIZE). Space Complexity: O(n * ALPHABET_SIZE) due to storage in `next_pos`.
Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Two-Pointer Greedy	O(n + m)	O(1)	Best choice for subsequence matching when only order matters
Dynamic Programming (LCS)	O(n × m)	O(n × m)	Useful when extending the problem to general subsequence comparisons

Frequently asked questions

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.

Append Characters to String to Make Subsequence solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Approach

Approach 2: Dynamic Programming Approach

Approach 3: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Append Characters to String to Make Subsequence solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Approach

Approach 2: Dynamic Programming Approach

Approach 3: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems