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
sandtconsisting of only lowercase English letters. Return the minimum number of characters that need to be appended to the end ofsso thattbecomes a subsequence ofs.
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^5sandtconsist 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;
}