Append Characters to String to Make Subsequence

Medium
1243.

Append Characters to String to Make Subsequence

Append Characters to String to Make Subsequence is a medium coding problem on strings, greedy and two pointers, asked in Amazon and Google interviews.

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^5
  • s and t consist only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var appendCharacters = function(s, t) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Append Characters to String to Make Subsequence

  1. Hint 1

    Appended characters can only help match a suffix of t; the part of t matched inside s must be a prefix.

  2. Hint 2

    So the question is: what is the longest prefix of t that is a subsequence of s?

  3. Hint 3

    Match greedily with two pointers — advance in t whenever the current character of s equals 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

  1. Set j = 0 (the next needed character of t).
  2. Scan s; whenever j < t.length and s[i] == t[j], increase j.
  3. 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 t can come from s.
  • Stop advancing j once all of t is matched.
  • Searching for each character of t from the start of s again 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) - j

Java

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