We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Append Characters to String to Make Subsequence

Number: 2572

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given two strings s and t consisting of only lowercase English letters, determine 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.

Key Insights

  • Use two pointers to iterate over s and t concurrently.
  • Match characters of t in s in order; every match moves the pointer for t.
  • The unmatched part of t (from the current pointer to the end) represents the characters needed to be appended.
  • This is a greedy approach ensuring the longest possible match of t in s.

Space and Time Complexity

Time Complexity: O(n + m), where n = len(s) and m = len(t).
Space Complexity: O(1)

Solution

We traverse string s with one pointer and string t with another pointer. For each character in s, if it matches the current character in t, advance the t pointer. After processing s, the remaining characters in t that were not matched must be appended to s. This direct two-pointer method efficiently determines the number of characters required for appending.

Code Solutions

# Python solution with line-by-line comments
def appendCharacters(s: str, t: str) -> int:
    i, j = 0, 0  # Initialize pointers for s and t
    # Traverse through s and t simultaneously
    while i < len(s) and j < len(t):
        # If characters match, move pointer in t to next character
        if s[i] == t[j]:
            j += 1
        i += 1  # Always move pointer in s
    # The remaining characters in t (from j to end) need to be appended
    return len(t) - j

# Test example
print(appendCharacters("coaching", "coding"))  # Expected output: 4
← Back to All Questions