Leetcode 2486: Append Characters to String to Make Subsequence

Input: Two strings s and t consisting only of lowercase English letters.

Example: s = "hello", t = "world"

Constraints:

• 1 <= s.length, t.length <= 10^5

• Both s and t consist only of lowercase English letters.

Output: Return the minimum number of characters that need to be appended to the end of string s so that t becomes a subsequence of s.

Example: Output: 4

Constraints:

• The returned value will be a non-negative integer.

Goal: Find the minimum number of characters to append to make t a subsequence of s.

Steps:

• 1. Initialize a pointer to iterate through string t.

• 2. Iterate through string s, and whenever a character in s matches the current character in t, move the pointer of t forward.

• 3. At the end, if all characters of t are found in s, return the difference between the length of t and the number of matched characters.

• 4. If not all characters of t are found in s, return the difference between the length of t and the number of matched characters.

Goal: The problem deals with strings of length up to 10^5, so the solution needs to be efficient.

Steps:

• 1 <= s.length, t.length <= 10^5

• Strings s and t consist only of lowercase English letters.

Assumptions:

• The solution assumes that both strings s and t contain only lowercase English letters.

• Input: s = "hello", t = "world"

• Explanation: For s = "hello" and t = "world", we need to append 'w', 'o', 'r', 'l', 'd' to the end of s to make t a subsequence of s.

• Input: s = "abcdef", t = "ace"

• Explanation: For s = "abcdef" and t = "ace", no characters need to be appended since t is already a subsequence of s.

• Input: s = "a", t = "abc"

• Explanation: For s = "a" and t = "abc", we need to append 'b', 'c' to the end of s to make t a subsequence of s.

Approach: We will use a two-pointer approach to efficiently find the subsequence. One pointer will iterate through string s, and the other pointer will iterate through string t. As we go through s, we will try to match characters from t.

Observations:

• We need to find how much of t is already a subsequence of s.

• If we can match all characters of t in s, we won't need to append anything.

• The key idea is to use the fact that matching characters in s with t can be tracked using a pointer on t. If the pointer reaches the end of t, it means t is already a subsequence of s.

Steps:

• 1. Initialize a pointer j to track characters in t.

• 2. Iterate through string s and check for matching characters in t.

• 3. For each match, move pointer j forward.

• 4. Once the iteration is done, the number of characters to append will be the difference between the length of t and j.

Empty Inputs:

• If t is empty, no characters need to be appended to s.

Large Inputs:

• For large strings (length up to 10^5), the solution must run in linear time O(n).

Special Values:

• If t is longer than s, all characters of t must be appended.

Constraints:

• The solution must handle inputs of size up to 10^5 efficiently.

int appendCharacters(string s, string t) {
    int j = 0;
    for(int i = 0; i < s.size() && j < t.size(); i++) {
        j += s[i] == t[j];
    }
    return t.size()-j;
}

1 : Function Declaration

int appendCharacters(string s, string t) {

This line defines the function `appendCharacters`, which takes two strings `s` and `t`, and returns an integer representing the number of characters to be appended to `s` to form `t.

2 : Variable Initialization

    int j = 0;

Here, we initialize the variable `j` to 0. This will be used to track how many characters of `t` match the suffix of `s`.

3 : Loop for Matching Characters

    for(int i = 0; i < s.size() && j < t.size(); i++) {

This `for` loop iterates through each character of string `s`, while `j` is less than the length of string `t`. It tries to find a matching suffix of `s` that corresponds to a prefix of `t`.

4 : Character Comparison

        j += s[i] == t[j];

This line compares the characters at the current position in both strings `s` and `t`. If they match, `j` is incremented. `j` thus keeps track of the length of the matching prefix of `t`.

5 : Return Statement

    return t.size()-j;

After the loop ends, we return the difference between the size of `t` and `j`. This represents the number of characters that need to be appended to `s` to make it equal to `t`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) where n is the length of string s, as we only need to iterate through s once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) as we only use a few variables for tracking pointers.

Leetcode 2486: Append Characters to String to Make Subsequence

Explore →