Append Characters to String to Make Subsequence

Med

#2268Time: O(N * M), where N is the length of `s` and M is the length of `t`. In the worst case, for each of the M characters in `t`, we might scan a large portion of `s`. Given the constraints, this would be too slow.Space: O(1), as we only use a few variables to store indices and counts.

Patterns

Two Pointers Greedy

Data structures

String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each character of the target string t and, for each character, searches for its first occurrence in the source string s starting from the position after the last match. This is repeated until a character from t cannot be found in the remaining part of s.

Algorithm

Initialize matched_count = 0 to count the characters of t found in s.
Initialize s_idx = 0 as the starting index for searching in s.
Iterate through each character t_char of t from left to right (index i from 0 to t.length() - 1).
Inside the loop, search for t_char in s starting from s_idx using a function like String.indexOf().
If t_char is found at position found_pos: a. Increment matched_count. b. Update s_idx to found_pos + 1 for the next search.
If t_char is not found, break the loop as the subsequence cannot be extended.
After the loop, matched_count holds the length of the longest prefix of t that is a subsequence of s.
Return t.length() - matched_count.

Walkthrough

The goal is to find the length of the longest prefix of t that is a subsequence of s. We can achieve this by iterating through t and for each character, finding its corresponding match in s.

We maintain a variable, s_idx, which keeps track of the starting index for our search in s. This ensures that we find characters in the correct order. Initially, s_idx is 0.

We loop through t from left to right. In each iteration, we use a string searching function (like Java's s.indexOf(char, fromIndex)) to find the current character of t in s, starting from s_idx.

If the character is found at some found_pos, we've extended our subsequence match. We then update s_idx to found_pos + 1 so the next search begins after the current match.
If the character is not found, it's impossible to extend the subsequence further, so we stop.

The total number of characters found this way gives the length of the longest prefix of t that is a subsequence of s. The final answer is the total length of t minus this matched length.

1class Solution {2    public int appendCharacters(String s, String t) {3        int t_len = t.length();4        int matched_count = 0;5        int s_idx = 0; // Start searching in s from this index6 7        for (int i = 0; i < t_len; i++) {8            char t_char = t.charAt(i);9            // Find the character in s starting from s_idx10            int found_pos = s.indexOf(t_char, s_idx);11 12            if (found_pos != -1) {13                // Found the character, update search index for the next character14                s_idx = found_pos + 1;15                matched_count++;16            } else {17                // Character not found, break the loop18                break;19            }20        }21        22        return t_len - matched_count;23    }24}

Complexity

Time

O(N * M), where N is the length of `s` and M is the length of `t`. In the worst case, for each of the M characters in `t`, we might scan a large portion of `s`. Given the constraints, this would be too slow.

Space

O(1), as we only use a few variables to store indices and counts.

Trade-offs

Pros

Simple to understand and implement, especially using built-in string functions.

Cons

Inefficient due to repeated scanning of the string s. The indexOf method may rescan parts of s in each iteration of the outer loop.

This is the most efficient approach. It uses two pointers, one for string s and one for string t, to find the longest prefix of t that is a subsequence of s in a single pass.

Algorithm

Initialize two pointers, i = 0 for string s and j = 0 for string t.
Use a while loop that continues as long as i is within the bounds of s and j is within the bounds of t.
Inside the loop, compare s.charAt(i) and t.charAt(j).
If they are equal, it's a match. Increment j to look for the next character in t.
Always increment i in each iteration to scan through s.
The loop terminates when either s is fully scanned (i == s.length()) or t is fully matched (j == t.length()).
The value of j at the end of the loop is the length of the longest prefix of t that is a subsequence of s.
The result is the number of characters in t that were not matched, which is t.length() - j.

Walkthrough

The core idea is to greedily match characters of t in s. We iterate through both strings simultaneously using two pointers.

We use a pointer i for s and a pointer j for t, both starting at index 0.

We traverse s with pointer i from left to right. At each character s.charAt(i), we check if it matches the character we are currently looking for from t, which is t.charAt(j).

If s.charAt(i) == t.charAt(j), it means we have found the j-th character of t in s. We then advance the pointer j to look for the next character of t.
Regardless of whether a match is found, we always advance the pointer i to move to the next character in s.

This process continues until we either exhaust s (i.e., i reaches s.length()) or we have found all characters of t (i.e., j reaches t.length()).

After the loop finishes, the value of j represents the number of characters from the beginning of t that were successfully found in s in the correct order. This is the length of the longest prefix of t that is a subsequence of s.

The number of characters we need to append to s is the number of characters in t that were not found, which is t.length() - j.

1class Solution {2    public int appendCharacters(String s, String t) {3        int i = 0; // pointer for s4        int j = 0; // pointer for t5        int n = s.length();6        int m = t.length();7 8        while (i < n && j < m) {9            if (s.charAt(i) == t.charAt(j)) {10                j++; // Match found, move to the next character in t11            }12            i++; // Always move to the next character in s13        }14 15        // j now holds the length of the longest prefix of t that is a subsequence of s.16        // The remaining characters of t must be appended.17        return m - j;18    }19}

Complexity

Time

O(N), where N is the length of `s`. The `while` loop iterates through `s` at most once, making the approach linear in the length of `s`. This is efficient enough to pass within the given constraints.

Space

O(1), as it only uses two integer pointers, requiring constant extra space.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Optimal solution as we must scan string s at least once.
Simple and elegant implementation with constant space usage.

Cons

There are no significant cons for this approach as it is optimal.

Solutions

Solution

1class Solution { public int appendCharacters ( String s , String t ) { int m = s . length (), n = t . length (); for ( int i = 0 , j = 0 ; j < n ; ++ j ) { while ( i < m && s . charAt ( i ) != t . charAt ( j )) { ++ i ; } if ( i ++ == m ) { return n - j ; } } return 0 ; } }

1class Solution { public: int appendCharacters ( string s , string t ) { int m = s . size (), n = t . size (); for ( int i = 0 , j = 0 ; j < n ; ++ j ) { while ( i < m && s [ i ] != t [ j ]) { ++ i ; } if ( i ++ == m ) { return n - j ; } } return 0 ; } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem