Scale Engineer

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 PointersGreedy
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 <= 105
  • 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

  1. Initialize matched_count = 0 to count the characters of t found in s.
  2. Initialize s_idx = 0 as the starting index for searching in s.
  3. Iterate through each character t_char of t from left to right (index i from 0 to t.length() - 1).
  4. Inside the loop, search for t_char in s starting from s_idx using a function like String.indexOf().
  5. 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.
  6. If t_char is not found, break the loop as the subsequence cannot be extended.
  7. After the loop, matched_count holds the length of the longest prefix of t that is a subsequence of s.
  8. 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.

class Solution {    public int appendCharacters(String s, String t) {        int t_len = t.length();        int matched_count = 0;        int s_idx = 0; // Start searching in s from this index         for (int i = 0; i < t_len; i++) {            char t_char = t.charAt(i);            // Find the character in s starting from s_idx            int found_pos = s.indexOf(t_char, s_idx);             if (found_pos != -1) {                // Found the character, update search index for the next character                s_idx = found_pos + 1;                matched_count++;            } else {                // Character not found, break the loop                break;            }        }                return t_len - matched_count;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem