# Append Characters to String to Make Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/append-characters-to-string-to-make-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/append-characters-to-string-to-make-subsequence
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## Problem
You are given two strings `s` and `t` consisting of only lowercase English letters.

Return _the minimum number of characters that need to be appended to the end of_ `s` _so that_ `t` _becomes a **subsequence** of_ `s`.

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 ("**co**aching**ding**").
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 ("**a**bcde").

**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 ("z**abcde**").
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 <= 105`
* `s` and `t` consist only of lowercase English letters.

# Approaches
## Brute Force with Iterative Search
This approach iterates through each character of the target string `t` and, for each character, searches for its first occurrence in the source string `s` starting from the position after the last match. This is repeated until a character from `t` cannot be found in the remaining part of `s`.
**Time:** O(N * M), where N is the length of `s` and M is the length of `t`. In the worst case, for each of the M characters in `t`, we might scan a large portion of `s`. Given the constraints, this would be too slow. · **Space:** O(1), as we only use a few variables to store indices and counts.
**Pros:** Simple to understand and implement, especially using built-in string functions.
**Cons:** Inefficient due to repeated scanning of the string `s`. The `indexOf` method may rescan parts of `s` in each iteration of the outer loop.
### Explanation
The goal is to find the length of the longest prefix of `t` that is a subsequence of `s`. We can achieve this by iterating through `t` and for each character, finding its corresponding match in `s`.

We maintain a variable, `s_idx`, which keeps track of the starting index for our search in `s`. This ensures that we find characters in the correct order. Initially, `s_idx` is 0.

We loop through `t` from left to right. In each iteration, we use a string searching function (like Java's `s.indexOf(char, fromIndex)`) to find the current character of `t` in `s`, starting from `s_idx`.

- If the character is found at some `found_pos`, we've extended our subsequence match. We then update `s_idx` to `found_pos + 1` so the next search begins after the current match.
- If the character is not found, it's impossible to extend the subsequence further, so we stop.

The total number of characters found this way gives the length of the longest prefix of `t` that is a subsequence of `s`. The final answer is the total length of `t` minus this matched length.

```java
class Solution {
    public int appendCharacters(String s, String t) {
        int t_len = t.length();
        int matched_count = 0;
        int s_idx = 0; // Start searching in s from this index

        for (int i = 0; i < t_len; i++) {
            char t_char = t.charAt(i);
            // Find the character in s starting from s_idx
            int found_pos = s.indexOf(t_char, s_idx);

            if (found_pos != -1) {
                // Found the character, update search index for the next character
                s_idx = found_pos + 1;
                matched_count++;
            } else {
                // Character not found, break the loop
                break;
            }
        }
        
        return t_len - matched_count;
    }
}
```
### Algorithm
1. Initialize `matched_count = 0` to count the characters of `t` found in `s`.
2. Initialize `s_idx = 0` as the starting index for searching in `s`.
3. Iterate through each character `t_char` of `t` from left to right (index `i` from 0 to `t.length() - 1`).
4. Inside the loop, search for `t_char` in `s` starting from `s_idx` using a function like `String.indexOf()`.
5. If `t_char` is found at position `found_pos`:
    a. Increment `matched_count`.
    b. Update `s_idx` to `found_pos + 1` for the next search.
6. If `t_char` is not found, break the loop as the subsequence cannot be extended.
7. After the loop, `matched_count` holds the length of the longest prefix of `t` that is a subsequence of `s`.
8. Return `t.length() - matched_count`.

## Optimal Two-Pointer Approach
This is the most efficient approach. It uses two pointers, one for string `s` and one for string `t`, to find the longest prefix of `t` that is a subsequence of `s` in a single pass.
**Time:** O(N), where N is the length of `s`. The `while` loop iterates through `s` at most once, making the approach linear in the length of `s`. This is efficient enough to pass within the given constraints. · **Space:** O(1), as it only uses two integer pointers, requiring constant extra space.
**Pros:** Highly efficient with a linear time complexity.; Optimal solution as we must scan string `s` at least once.; Simple and elegant implementation with constant space usage.
**Cons:** There are no significant cons for this approach as it is optimal.
### Explanation
The core idea is to greedily match characters of `t` in `s`. We iterate through both strings simultaneously using two pointers.

We use a pointer `i` for `s` and a pointer `j` for `t`, both starting at index 0.

We traverse `s` with pointer `i` from left to right. At each character `s.charAt(i)`, we check if it matches the character we are currently looking for from `t`, which is `t.charAt(j)`.

- If `s.charAt(i) == t.charAt(j)`, it means we have found the `j`-th character of `t` in `s`. We then advance the pointer `j` to look for the next character of `t`.
- Regardless of whether a match is found, we always advance the pointer `i` to move to the next character in `s`.

This process continues until we either exhaust `s` (i.e., `i` reaches `s.length()`) or we have found all characters of `t` (i.e., `j` reaches `t.length()`).

After the loop finishes, the value of `j` represents the number of characters from the beginning of `t` that were successfully found in `s` in the correct order. This is the length of the longest prefix of `t` that is a subsequence of `s`.

The number of characters we need to append to `s` is the number of characters in `t` that were not found, which is `t.length() - j`.

```java
class Solution {
    public int appendCharacters(String s, String t) {
        int i = 0; // pointer for s
        int j = 0; // pointer for t
        int n = s.length();
        int m = t.length();

        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                j++; // Match found, move to the next character in t
            }
            i++; // Always move to the next character in s
        }

        // j now holds the length of the longest prefix of t that is a subsequence of s.
        // The remaining characters of t must be appended.
        return m - j;
    }
}
```
### Algorithm
1. Initialize two pointers, `i = 0` for string `s` and `j = 0` for string `t`.
2. Use a `while` loop that continues as long as `i` is within the bounds of `s` and `j` is within the bounds of `t`.
3. Inside the loop, compare `s.charAt(i)` and `t.charAt(j)`.
4. If they are equal, it's a match. Increment `j` to look for the next character in `t`.
5. Always increment `i` in each iteration to scan through `s`.
6. The loop terminates when either `s` is fully scanned (`i == s.length()`) or `t` is fully matched (`j == t.length()`).
7. The value of `j` at the end of the loop is the length of the longest prefix of `t` that is a subsequence of `s`.
8. The result is the number of characters in `t` that were not matched, which is `t.length() - j`.

# Solutions
### Java

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

### CPP

```cpp
class Solution { public: int appendCharacters ( string s , string t ) { int m = s . size (), n = t . size (); for ( int i = 0 , j = 0 ; j < n ; ++ j ) { while ( i < m && s [ i ] != t [ j ]) { ++ i ; } if ( i ++ == m ) { return n - j ; } } return 0 ; } };
```

### Python

```python
class Solution : def appendCharacters ( self , s : str , t : str ) -> int : i , m = 0 , len ( s ) for j , c in enumerate ( t ): while i < m and s [ i ] != c : i += 1 if i == m : return len ( t ) - j i += 1 return 0
```