Sponsored
Sponsored
This approach uses two pointers to scan both strings, one pointer for each string. The idea is to attempt to match characters of t with those in s. A character from t is successfully matched if it is equal to the current character in s. We iterate through s, moving the pointer for each character matched, while the pointer for t only moves if a match is found. Once we've iterated through s, we determine how many characters are left unmatched in t, which is the number of characters needed to be appended to s.
Time Complexity: O(n + m) where n is the length of s and m is the length of t.
Space Complexity: O(1) as no additional space is used.
1#include <iostream>
2#include <string>
3
4int minCharsToAppend(const std::string& s, const std::string& t) {
5 int sLen = s.length();
6 int tLen = t.length();
7 int sIndex = 0, tIndex = 0;
8
9 while (sIndex < sLen && tIndex < tLen) {
10 if (s[sIndex] == t[tIndex]) {
11 tIndex++;
12 }
13 sIndex++;
14 }
return tLen - tIndex;
}
int main() {
std::string s = "coaching";
std::string t = "coding";
std::cout << minCharsToAppend(s, t) << std::endl;
return 0;
}The C++ solution follows a similar logic as the C solution, utilizing two indices to scan both strings. The function minCharsToAppend calculates the number of characters in t that could not be matched with those in s and returns that number.
This approach uses dynamic programming to precompute the next occurrence of each character for every position in the string s. By doing so, we quickly identify the existence and location of each character from t in s. We build a 2D array next where next[i][j] represents the smallest index >= i that holds the character j in s. This helps in efficiently determining the position of characters and the necessary additions to the end of the string.
Time Complexity: O(n + m + n * ALPHABET_SIZE) due to preprocessing each character for positions.
Space Complexity: O(n * ALPHABET_SIZE) used by the 2D array next where n is length of s.
1using System;
2
3public class MinChars
4{
5 public static int MinCharsToAppend(string s, string t)
6 {
7 int sLen = s.Length;
8 int tLen = t.Length;
9 int[,] next = new int[sLen + 1, 26];
10
11 for (int i = 0; i <= sLen; i++)
12 for (int j = 0; j < 26; j++)
13 next[i, j] = sLen;
14
15 int[] last = new int[26];
16 for (int i = 0; i < 26; i++) last[i] = sLen;
17
18 for (int i = sLen - 1; i >= 0; i--) {
19 last[s[i] - 'a'] = i;
20 for (int j = 0; j < 26; j++)
21 next[i, j] = last[j];
22 }
23
24 int pos = 0, appendCount = 0;
25 for (int i = 0; i < tLen; i++) {
26 if (next[pos, t[i] - 'a'] == sLen) {
27 appendCount += (tLen - i);
28 break;
29 }
30 pos = next[pos, t[i] - 'a'] + 1;
31 }
32
33 return appendCount;
34 }
35
36 public static void Main()
37 {
38 string s = "coaching";
39 string t = "coding";
40 Console.WriteLine(MinCharsToAppend(s, t));
41 }
42}The C# solution works by building the next table, precomputing where each character can next be found, and uses this table to determine the remaining characters in t that need appending into s to maintain order.