2486. Append Characters to String to Make Subsequence

MediumGreedyTwo PointersString
Leetcode Link

Problem Description

In this problem, we're given two strings s and t, which consist only of lowercase English letters. Our task is to determine the minimum number of characters we must append to the end of s to make t a subsequence of s. To clarify, a subsequence of a string is a new string that's formed from the original string by deleting some (possibly no) characters without changing the order of the remaining characters. For example, if s is "abcde" and t is "ace", then t is already a subsequence of s, and we don't need to append any characters. However, if s is "abc" and t is "dabc", we'd need to append a "d" at the start. Since the problem only allows appending at the end, we count the number of characters in t that are not yet in s as a subsequence, and that's the number we must append.

Intuition

The solution for this problem is based on the two-pointer technique, which is often used for problems involving sequences or arrays. The key idea is to iterate through both strings s and t simultaneously using two pointers (or indices) and find the parts of t that are already a subsequence in s. Whenever we find that a character in t does not match any further characters in s (because we've reached the end of s without finding a match), we realize that the remaining characters of t must be appended to s.

We use two pointers–i for tracking the position in s and j for tracking the position in t. We increment i to find a match for t[j] in s. If we reach the end of s (i == m) before finding a match, it means the rest of t starting from t[j] must be appended to s. If we successfully find a match for every character in t, it implies that t is already a subsequence of s, and no characters need to be appended.

The solution method effectively compares each character of t with the characters in s, ensuring the subsequence order of t in s. The number of iterations (advance of the pointer) in s gives us the minimal insertions at the end of s to make t a subsequence.

Learn more about Greedy and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The solution uses a straightforward approach without any additional data structures, relying only on two indices to traverse the strings.

Here's a step-by-step explanation of how the code works:

  1. Initialize two pointers: i starting at 0 for string s, and j also starting at 0 for string t. These pointers are used to traverse each string.
  2. Begin a loop over string t using j as the loop index. For each character t[j] in t:
    • Increment i to find a matching character in s. We move i forward as long as i < m (not at the end of s) and s[i] is not equal to t[j]. This is done with while i < m and s[i] != t[j]: i += 1.
    • Once a character in s matches t[j], or we have reached the end of s, we proceed to check if we have exhausted s. If i == m, it means that there are no more characters left in s to match with t[j], hence the remaining characters of t need to be appended.
      • In this case, we return n - j, where n is the length of t, and j is the current index. n - j gives us the count of additional characters needed from t to complete the subsequence.
    • If a match is found, and i has not reached the end of s, we increment the pointer i to continue searching for the next characters of t.
  3. After the loop, if all characters in t have a corresponding character in s, then we do not need to append any additional characters. Hence we return 0.

The algorithm's time complexity is O(n + m) where n is the length of t and m is the length of s, because in the worst case we might have to traverse both strings entirely. No extra space is needed except for the pointers, so the space complexity is O(1).

This approach is efficient because it minimizes the number of operations and only uses memory for the pointers to the current character in both strings s and t. It uses the inherent order of the input strings to find the solution without backtracking, making it an elegant solution for the given problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose s is "xyza" and t is "ayz".

  1. Initialize two pointers: i = 0 for "xyza" (s) and j = 0 for "ayz" (t).
  2. We are now looking to match "a" from t in s. Since s[0] is "x", and "x" ≠ "a", we increment i.
  3. i = 1 and s[1] is "y", and "y" ≠ "a", we increment i again.
  4. i = 2 and s[2] is "z", and "z" ≠ "a", we increment i once more.
  5. i = 3 and s[3] is "a", and "a" = "a", we found our first match. Now, we increment j to look for the next character in t.
  6. j = 1 and t[1] is "y". i is also moved to look for "y" in s.
  7. i stays at 3 because "a" = s[3] and "a" ≠ "y", but we cannot increment i anymore since we have reached the end of s.
  8. Since i == m (length of s), we realize that we need to append the remaining characters of t starting from t[j] to s.
  9. Therefore, we return n - j, which is the length of t (n = 3) minus the current index of t (j = 1), giving us 3 - 1 = 2. So, we must append two characters, "yz", to s.

This example confirms that the minimum number of characters we must append to s to make t a subsequence is 2, with the result being "xyzayz". The result does not have to be the original t; it only needs to contain t as a subsequence.

Solution Implementation

1class Solution:
2    def appendCharacters(self, s: str, t: str) -> int:
3        # Initialize the lengths of strings s and t
4        s_length, t_length = len(s), len(t)
5        # Initialize the index for string s
6        index_s = 0
7      
8        # Iterate over each character in string t
9        for index_t in range(t_length):
10            # Move index_s in string s until the character matches the current character in string t
11            while index_s < s_length and s[index_s] != t[index_t]:
12                index_s += 1
13          
14            # If index_s has reached the end of s, return the remaining number of characters in t
15            # that need to be appended to s to make t a substring of the modified s
16            if index_s == s_length:
17                return t_length - index_t
18          
19            # Move to the next character in s after a match is found
20            index_s += 1
21      
22        # If all characters in t are matched before reaching the end of s, no characters need to be appended
23        return 0
24
1class Solution {
2    public int appendCharacters(String s, String t) {
3        // m is the length of string s
4        int lengthS = s.length();
5        // n is the length of string t
6        int lengthT = t.length();
7      
8        // Initialize pointers for both strings
9        // i for traversing s, j for traversing t
10        int i = 0, j = 0;
11
12        // Iterate through string t to find if characters are in string s
13        while (j < lengthT) {
14            // Move i forward in string s until character at s[i] matches t[j],
15            // or until the end of s is reached
16            while (i < lengthS && s.charAt(i) != t.charAt(j)) {
17                i++;
18            }
19
20            // If the end of s is reached before finding a match, return 
21            // the number of remaining characters to append from t to s
22            if (i++ == lengthS) {
23                return lengthT - j;
24            }
25
26            // Move j forward to the next character in t
27            j++;
28        }
29
30        // If we reach here, all characters of t are matched in order within s,
31        // so there is no need to append any characters, hence return 0
32        return 0;
33    }
34}
35
1class Solution {
2public:
3    int appendCharacters(string s, string t) {
4        int m = s.size(); // Length of string s
5        int n = t.size(); // Length of string t
6      
7        // Initialize pointers for strings s (i) and t (j)
8        for (int i = 0, j = 0; j < n; ++j) {
9            // Increment i until we find a matching character in s for t[j]
10            while (i < m && s[i] != t[j]) {
11                ++i;
12            }
13            // If we reach the end of s, return how many characters to append from t
14            if (i == m) {
15                return n - j;
16            }
17            // Move to the next character in s
18            i++;
19        }
20        // If all characters of t are found in s in order, no need to append any character
21        return 0;
22    }
23};
24
1function appendCharacters(s: string, t: string): number {
2    let m = s.length; // Length of string s
3    let n = t.length; // Length of string t
4  
5    // Initialize pointers for strings s (i) and t (j)
6    let i = 0, j = 0;
7    while (j < n) {
8        // Increment i until we find a matching character in s for t[j]
9        while (i < m && s[i] !== t[j]) {
10            i++;
11        }
12        // If we reach the end of s, return how many characters to append from t
13        if (i === m) {
14            return n - j;
15        }
16        // Move to the next character in s and t
17        i++;
18        j++;
19    }
20    // If all characters of t are found in s in the given order, no need to append any character
21    return 0;
22}
23
Not Sure What to Study? Take the 2-min Quiz：

How does merge sort divide the problem into subproblems?

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed by looking at the nested loops (represented implicitly through the sequential searches within the string s):

  • For each character in string t (n characters total), the code potentially iterates through the entirety of string s (m characters) to find a matching character.
  • In the worst case, each character of t will be compared to each character in s until a match is found or until the end of s is reached.
  • Therefore, the worst-case scenario would result in a time complexity of O(m*n), where m is the length of the string s and n is the length of the string t.

Space Complexity

The space complexity of the code is quite straightforward:

  • The code uses only a fixed number of variables (m, n, i, and j) to keep track of the indices and lengths of the strings s and t.
  • No additional data structures are created that grow in size with the input.
  • Thus, the space complexity is O(1), which means it is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫