Append Characters to String to Make Subsequence — Solution
Append Characters to String to Make Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Append Characters to String to Make Subsequence is a medium coding problem on strings, greedy and two pointers, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two lowercase strings s and t. You may append characters to the end of s.
Return the minimum number of characters you must append so that t becomes a subsequence of s — that is, t can be obtained from the new s by deleting some (possibly no) characters without changing the order of the rest.
Example 1
Input: s = "codekairo", t = "codex"
Output: 1
Explanation: `"code"` already appears in order; only `x` must be appended.
Example 2
Input: s = "abc", t = "xyz"
Output: 3
Example 3
Input: s = "kairo", t = "kio"
Output: 0
Explanation: `k`, `i` and `o` already appear in order.
Constraints
1 <= s.length, t.length <= 10^5s and t consist only of lowercase English letters
Hints for Append Characters to String to Make Subsequence
Hint 1
Appended characters can only help match a suffix of
t; the part oftmatched insidesmust be a prefix.Hint 2
So the question is: what is the longest prefix of
tthat is a subsequence ofs?Hint 3
Match greedily with two pointers — advance in
twhenever the current character ofsequals the next needed one. Append the rest.
How to solve Append Characters to String to Make Subsequence
Whatever is appended goes after all of s, so s must cover a prefix of t and the rest is appended. Greedy two-pointer matching finds the longest prefix of t that is a subsequence of s.
Approach
- Set
j = 0(the next needed character oft). - Scan
s; wheneverj < t.lengthands[i] == t[j], increasej. - Return
t.length - j.
Why it works
Taking the earliest possible match for each character of t never hurts: it leaves the largest possible remainder of s for the following characters. So after the scan j is the length of the longest prefix of t that s contains as a subsequence. The remaining t.length - j characters cannot be matched inside s, and appending exactly them is enough.
Complexity
- Time —
O(|s| + |t|) - Space —
O(1)
Pitfalls
- Characters can only be appended at the end, not inserted, so only a prefix of
tcan come froms. - Stop advancing
jonce all oftis matched. - Searching for each character of
tfrom the start ofsagain is wrong — order must be preserved.
Reference solution
Python
def appendCharacters(s: str, t: str) -> int:
j = 0
for ch in s:
if j < len(t) and ch == t[j]:
j += 1
return len(t) - jJava
public static int appendCharacters(String s, String t) {
int j = 0;
for (int i = 0; i < s.length() && j < t.length(); i++) if (s.charAt(i) == t.charAt(j)) j++;
return t.length() - j;
}C++
int appendCharacters(string s, string t) {
size_t j = 0;
for (size_t i = 0; i < s.size() && j < t.size(); i++) if (s[i] == t[j]) j++;
return (int)(t.size() - j);
}JavaScript
var appendCharacters = function(s, t) {
var j = 0;
for (var i = 0; i < s.length && j < t.length; i++) if (s[i] === t[j]) j++;
return t.length - j;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms