Append Characters to String to Make Subsequence

Problem Statement

In the problem, we are given two strings, s and t, comprised solely of lowercase English letters. The goal is to determine the minimum number of characters that need to be appended to the end of string s so that string t becomes a subsequence of s. By definition, a subsequence of a string can be formed by deleting some or none of the characters from the string without rearranging the remaining characters. For instance, "ace" is a subsequence of "abcde" but "aec" is not.

Examples

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.

Approach and Intuition

The core of solving this problem lies in understanding how t can fit within s by potentially appending characters to s. The approach involves sequentially checking if each character of t can be found in s in order. Here's a breakdown of the intuition and steps:

Examples

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.

Step-by-Step Approach:

1. Pointer Utilization:

   • Use two pointers: one (i) for traversing s and another (j) for traversing t.

2. Sequential Matching:

   • Traverse through s checking for the presence of characters that match with current t[j]. If found, move pointer j to the next character of t.

3. Trace Subsequence Formation:

   • Continue scanning through s until:
     • We have either identified all characters of t in order within s (making t a subsequence already), or
     • We reach the end of s with characters of t still unmatched.

4. Check Remaining Characters of t:

   • If after traversing s there are still remaining characters in t:
     • The count of these remaining characters is essentially the number we need to append to s.

5. Final Output:

   • If j reaches the end of t (indicating every character of t has a corresponding match in order found in s), then return 0, as t is already a subsequence of s.
   • Otherwise, return the number of characters from t that were not matched—these need to be appended to s.

Examples Revisited:

From the provided examples:

• In Example 1, not all characters of "coding" can be found in order in "coaching". Only after appending "ding" does "coding" fit as a subsequence within "coachingding".
• In Example 2, "a" is already a subsequence of "abcde", so we append 0 characters.
• In Example 3, none of the characters of "abcde" are matched in "z", we therefore need to append all characters "abcde" to make it a subsequence.

This structured approach, targeting the formation of subsequences by sequential matching and appending, effectively solves the problem within the constraints given.

Solutions

class Solution {
public:
    int addCharacters(string str1, string str2) {
        int index1 = 0, maxPrefix = 0;
    
        while (index1 < str1.size() && maxPrefix < str2.size()) {
            if (str1[index1] == str2[maxPrefix]) {
                maxPrefix++;
            }
            index1++;
        }
    
        return str2.size() - maxPrefix;
    }
};