2486. Accept Characters to String to Make Subsequence

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Two Pointer、String、Greedy
  • \(\color{blue}\textsf{Weekly Contest 321}\)

一、題目

  • You are given two strings s and t consisting of only lowercase English letters. Return 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.

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 <= 10^5
  • s and t consist only of lowercase English letters.

二、分析

  • 這一題是簡單的 Two Pointer，當 s[i] == t[j] 時，j++。i 指標走到盡頭時，t 剩餘多少字元即為 s 需要增加的字元。

三、解題

1. Two Pointer

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
int appendCharacters(string s, string t) {
    int i = 0, j = 0;
    for (; i < s.length(); i++) {
        if (s[i] == t[j]) j++;
        if (j == t.length()) return 0;
    }
    return t.length()-j;
}

回目錄 Catalog