Append Characters to String to Make Subsequence
Find the minimum number of characters to append to s so that t becomes a subsequence — count unmatched suffix of t.
3 min read
two-pointers string greedy
Problem#
Return the minimum number of characters to append to the end of s so that t becomes a subsequence of s.
Examples#
s = "coaching", t = "coding"→4(s + "ding"makes"coding"a subsequence)s = "abcde", t = "a"→0s = "z", t = "abcde"→5
Constraints#
1 <= s.length, t.length <= 10^5, lowercase.
Hints#
Hint 1
Greedy match
t against s left to right with two pointers; return the leftover length of t. Approach#
Run the standard subsequence-matching two-pointer. Whatever portion of t remains unmatched is exactly what must be appended.
Solution#
class Solution {public: int appendCharacters(string s, string t) { int i = 0, j = 0; const int n = s.size(), m = t.size(); while (i < n && j < m) { if (s[i] == t[j]) ++j; ++i; } return m - j; }};func appendCharacters(s string, t string) int { i, j := 0, 0 n, m := len(s), len(t) for i < n && j < m { if s[i] == t[j] { j++ } i++ } return m - j}class Solution: def appendCharacters(self, s: str, t: str) -> int: j = 0 m = len(t) for ch in s: if j < m and ch == t[j]: j += 1 if j == m: break return m - jvar appendCharacters = function(s, t) { let i = 0, j = 0; const n = s.length, m = t.length; while (i < n && j < m) { if (s[i] === t[j]) j++; i++; } return m - j;};class Solution { public int appendCharacters(String s, String t) { int i = 0, j = 0; int n = s.length(), m = t.length(); while (i < n && j < m) { if (s.charAt(i) == t.charAt(j)) j++; i++; } return m - j; }}function appendCharacters(s: string, t: string): number { let i = 0, j = 0; const n = s.length, m = t.length; while (i < n && j < m) { if (s[i] === t[j]) j++; i++; } return m - j;}Editorial#
Subsequence matching is greedy: when s[i] matches t[j], advance both — there is never a benefit to deferring a match (any character we skip in t will need to be appended). After the walk, j indexes the first unmatched character of t, so m - j is the count of characters that couldn’t be matched.
Complexity#
- Time: O(n + m).
- Space: O(1).
Concept revision#
Related#