< Back





2486. Append Characters to String to Make Subsequence

Given two strings, s and t, we're asked to add characters to s to make t a subsequence of s. A
subsequence is not a substring, the characters don't have to be contiguous, however, they do need to
be in the same order as they appear in t.

This is a greedy problem. By default, we're going to assume that all the characters in t need to be
appended to s to make t a subsequence of s. Then we're going to traverse s and t from left to right,
checking the characters at each position. We're essentially seeing if the characters in t appear in
the same as order as s.

If s[i] == t[j], we've got a match and so we decrement our answer, the number of characters we need
to append to s is less now because the character found in t is in the same order as s. We increment
j, we're now looking at the next character in t. By default, we'll always increment i.

By the end of this iteration, we'll have found all the characters in s that appear in the same order
as t, and subtracted them from our answer - we don't need to append them. The remaining answer is
the number of characters we need to append to s to make t a subsequence of s.

The solution is as follows:


  class Solution:
      def appendCharacters(self, s: str, t: str) -> int:
          m, n = len(s), len(t)
          ans = n
          i = j = 0

          while i < m and j < n:
              if s[i] == t[j]:
                  ans -= 1
                  j += 1

              i += 1

          return ans


_ Time Complexity:

  O(n) - We iterate over each character in s.

_ Space Complexity:

  O(1) - We store our answer in a single variable.