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.

Examples

Example 1:

1
2

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 ("coachingding"). It can be shown that appending any 3 characters to the end of s will never make t a subsequence.

Example 2:

1
2

Input: s = "abcde", t = "a"
Output: 0

Explanation: t is already a subsequence of s ("abcde").

Example 3:

1
2

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 (“zabcde”). It can be shown that appending any 4 characters to the end of s will never make t a subsequence.

Solution

Method 1 - Two Pointer Technique

  1. compute the lengths for s, t store in |s|, |t|.
  2. Transverse the whole string s with control variable i, & move the pointer j when s[i]==t[j]
  3. Finally, we return the length of unmatched string in t, aka |t|-j is the answer

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)