Append Characters to String to Make Subsequence

medium string two pointers greedy

Problem

You are given two strings s and t made of lowercase letters. In one operation you may append any single character to the end of s. Return the minimum number of such appends needed so that t becomes a subsequence of s. A subsequence keeps the characters of t in order, but they need not be next to each other in s.

Inputs = "coaching", t = "code"

Output2

Scanning s we can match "c" then "o" of t, but "d" and "e" never appear afterward. Appending "de" gives "coachingde", which contains "code" as a subsequence, so 2 appends are needed.

def append_characters(s, t):
    j = 0
    for ch in s:
        if j < len(t) and ch == t[j]:
            j += 1
    return len(t) - j

function appendCharacters(s, t) {
  let j = 0;
  for (let i = 0; i < s.length; i++) {
    if (j < t.length && s[i] === t[j]) j++;
  }
  return t.length - j;
}

class Solution {
    public int appendCharacters(String s, String t) {
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            if (j < t.length() && s.charAt(i) == t.charAt(j)) j++;
        }
        return t.length() - j;
    }
}

int appendCharacters(string s, string t) {
    int j = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (j < (int)t.size() && s[i] == t[j]) j++;
    }
    return (int)t.size() - j;
}

Explanation

We can only add characters to the end of s, so the prefix of t that we still need is whatever cannot already be found inside s as a subsequence. The whole task is to figure out how many leading characters of t we can match against s.

Walk a single pointer j across t and scan s from left to right. Each time the current character of s equals t[j], that letter of t is satisfied, so we advance j by one. Characters of s that do not match are simply skipped — they cannot hurt us.

This greedy match is optimal: matching t[j] at the earliest possible position in s leaves the most room to match the rest of t later, so no other strategy can match more characters.

When the scan ends, j tells us how many leading characters of t were matched. The remaining len(t) - j characters were never found, and since appends only add to the tail, those leftover characters are exactly what we must append.

Example: s = "coaching", t = "code". We match c at index 0 and o at index 1, then d never appears, so j stops at 2. The answer is 4 - 2 = 2, matching the appended suffix "de".

Time: O(n + m) Space: O(1)