Vultr DocsLatest Content

Append Characters to String to Make Subsequence

Updated on 20 May, 2025
Append Characters to String to Make Subsequence header image

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

  • C++
  • Java
  • Python
cpp 
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;
    }
};

The given C++ solution addresses the problem of modifying a string to make it a subsequence of another string. Specifically, this program defines a method addCharacters that determines the minimum number of characters you need to append to str1 to make it a subsequence of str2.

The function utilizes two integer variables, index1 and maxPrefix, to track the current position within each string. The process starts at the beginning of both strings and iterates through str1. For each character in str1, it checks if it matches the current character in str2 pointed by maxPrefix. If a match occurs, maxPrefix is incremented to point to the next character in str2, thereby extending the current matching prefix.

The loop continues until the end of str1 or until all characters in str2 have found a match in str1. The returned result, str2.size() - maxPrefix, represents the count of additional characters from str2 that need to be appended to str1 to extend the matching prefix to the entire length of str2.

This efficiently ensures that:

  • You understand how many more characters are required from str2 to make str1 a valid subsequence of str2.
  • The computational overhead remains limited, as the solution operates linearly with respect to the lengths of str1 and str2.
java 
class Solution {
    
    public int combineStrings(String str1, String str2) {
        int index1 = 0, prefixMatch = 0;
    
        while (index1 < str1.length() && prefixMatch < str2.length()) {
            if (str1.charAt(index1) == str2.charAt(prefixMatch)) {
                prefixMatch++;
            }
            index1++;
        }
    
        return str2.length() - prefixMatch;
    }
}

The Java function combineStrings in the provided code calculates the minimum number of characters that need to be appended to one string (str1) to ensure that another string (str2) becomes a subsequence of str1. Here’s how you understand the code:

  • Initialize two counters: index1 for traversing str1 and prefixMatch for tracking matches with str2.
  • Use a while loop to iterate through both strings as long as index1 is less than the length of str1 and prefixMatch is less than the length of str2.
  • Inside the loop, compare characters from both strings:
    • If characters at the current positions match (str1.charAt(index1) == str2.charAt(prefixMatch)), increment the prefixMatch counter.
    • Always increment the index1 counter to continue scanning str1.
  • After exiting the loop, the remaining unmatched portion of str2 is calculated by subtracting prefixMatch from the total length of str2.
  • The result, which is the number of characters from str2 that haven’t been matched in str1, is returned. This number represents the additional characters needed to append to str1 to make str2 a subsequence.
python 
class Solution:
    def concatenateSuffix(self, string1: str, string2: str) -> int:
        idx1 = 0
        matching_count = 0
    
        while idx1 < len(string1) and matching_count < len(string2):
            if string1[idx1] == string2[matching_count]:
                matching_count += 1
            idx1 += 1
    
        return len(string2) - matching_count

The given Python solution addresses the problem of determining how many characters need to be appended to a string (string1) to make another string (string2) a subsequence of it. The implementation works as follows:

  • Initialize two pointers: idx1 for iterating over string1 and matching_count for tracking the number of characters from string2 that have been matched with string1.
  • Use a while loop to iterate through string1 while the matching_count is less than the length of string2. During each iteration, check if the current character of string1 matches the current character of string2 pointed to by matching_count.
  • If a match is found, increase the matching_count to check for the next character in the next cycle.
  • At the end of the loop, subtract the final matching_count from the length of string2 to find out how many more characters are needed to be appended to string1 to make string2 a subsequence.

The efficiency of this solution lies in its linear scanning of both strings, making it optimal for larger inputs. This method successfully calculates the minimum number of characters that need to be added to string1 to include string2 as a subsequence.

Comments