2486. Append Characters to String to Make Subsequence
Problem Description
In this problem, we're given two strings s
and t
, which consist only of lowercase English letters. Our task is to determine the minimum number of characters we must append to the end of s
to make t
a subsequence of s
. To clarify, a subsequence of a string is a new string that's formed from the original string by deleting some (possibly no) characters without changing the order of the remaining characters. For example, if s
is "abcde" and t
is "ace", then t
is already a subsequence of s
, and we don't need to append any characters. However, if s
is "abc" and t
is "dabc", we'd need to append a "d" at the start. Since the problem only allows appending at the end, we count the number of characters in t
that are not yet in s
as a subsequence, and that's the number we must append.
Intuition
The solution for this problem is based on the two-pointer technique, which is often used for problems involving sequences or arrays. The key idea is to iterate through both strings s
and t
simultaneously using two pointers (or indices) and find the parts of t
that are already a subsequence in s
. Whenever we find that a character in t
does not match any further characters in s
(because we've reached the end of s
without finding a match), we realize that the remaining characters of t
must be appended to s
.
We use two pointersāi
for tracking the position in s
and j
for tracking the position in t
. We increment i
to find a match for t[j]
in s
. If we reach the end of s
(i == m
) before finding a match, it means the rest of t
starting from t[j]
must be appended to s
. If we successfully find a match for every character in t
, it implies that t
is already a subsequence of s
, and no characters need to be appended.
The solution method effectively compares each character of t
with the characters in s
, ensuring the subsequence order of t
in s
. The number of iterations (advance of the pointer) in s
gives us the minimal insertions at the end of s
to make t
a subsequence.
Learn more about Greedy and Two Pointers patterns.
Solution Approach
The solution uses a straightforward approach without any additional data structures, relying only on two indices to traverse the strings.
Here's a step-by-step explanation of how the code works:
- Initialize two pointers:
i
starting at 0 for strings
, andj
also starting at 0 for stringt
. These pointers are used to traverse each string. - Begin a loop over string
t
usingj
as the loop index. For each charactert[j]
int
:- Increment
i
to find a matching character ins
. We movei
forward as long asi < m
(not at the end ofs
) ands[i]
is not equal tot[j]
. This is done withwhile i < m and s[i] != t[j]: i += 1
. - Once a character in
s
matchest[j]
, or we have reached the end ofs
, we proceed to check if we have exhausteds
. Ifi == m
, it means that there are no more characters left ins
to match witht[j]
, hence the remaining characters oft
need to be appended.- In this case, we return
n - j
, wheren
is the length oft
, andj
is the current index.n - j
gives us the count of additional characters needed fromt
to complete the subsequence.
- In this case, we return
- If a match is found, and
i
has not reached the end ofs
, we increment the pointeri
to continue searching for the next characters oft
.
- Increment
- After the loop, if all characters in
t
have a corresponding character ins
, then we do not need to append any additional characters. Hence we return0
.
The algorithm's time complexity is O(n + m)
where n
is the length of t
and m
is the length of s
, because in the worst case we might have to traverse both strings entirely. No extra space is needed except for the pointers, so the space complexity is O(1)
.
This approach is efficient because it minimizes the number of operations and only uses memory for the pointers to the current character in both strings s
and t
. It uses the inherent order of the input strings to find the solution without backtracking, making it an elegant solution for the given problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose s
is "xyza" and t
is "ayz".
- Initialize two pointers:
i = 0
for "xyza" (s) andj = 0
for "ayz" (t). - We are now looking to match "a" from
t
ins
. Sinces[0]
is "x", and "x" ā "a", we incrementi
. i = 1
ands[1]
is "y", and "y" ā "a", we incrementi
again.i = 2
ands[2]
is "z", and "z" ā "a", we incrementi
once more.i = 3
ands[3]
is "a", and "a" = "a", we found our first match. Now, we incrementj
to look for the next character int
.j = 1
andt[1]
is "y".i
is also moved to look for "y" ins
.i
stays at3
because "a" =s[3]
and "a" ā "y", but we cannot incrementi
anymore since we have reached the end ofs
.- Since
i == m
(length ofs
), we realize that we need to append the remaining characters oft
starting fromt[j]
tos
. - Therefore, we return
n - j
, which is the length oft
(n = 3
) minus the current index oft
(j = 1
), giving us3 - 1 = 2
. So, we must append two characters, "yz", tos
.
This example confirms that the minimum number of characters we must append to s
to make t
a subsequence is 2, with the result being "xyzayz". The result does not have to be the original t
; it only needs to contain t
as a subsequence.
Solution Implementation
1class Solution:
2 def appendCharacters(self, s: str, t: str) -> int:
3 # Initialize the lengths of strings s and t
4 s_length, t_length = len(s), len(t)
5 # Initialize the index for string s
6 index_s = 0
7
8 # Iterate over each character in string t
9 for index_t in range(t_length):
10 # Move index_s in string s until the character matches the current character in string t
11 while index_s < s_length and s[index_s] != t[index_t]:
12 index_s += 1
13
14 # If index_s has reached the end of s, return the remaining number of characters in t
15 # that need to be appended to s to make t a substring of the modified s
16 if index_s == s_length:
17 return t_length - index_t
18
19 # Move to the next character in s after a match is found
20 index_s += 1
21
22 # If all characters in t are matched before reaching the end of s, no characters need to be appended
23 return 0
24
1class Solution {
2 public int appendCharacters(String s, String t) {
3 // m is the length of string s
4 int lengthS = s.length();
5 // n is the length of string t
6 int lengthT = t.length();
7
8 // Initialize pointers for both strings
9 // i for traversing s, j for traversing t
10 int i = 0, j = 0;
11
12 // Iterate through string t to find if characters are in string s
13 while (j < lengthT) {
14 // Move i forward in string s until character at s[i] matches t[j],
15 // or until the end of s is reached
16 while (i < lengthS && s.charAt(i) != t.charAt(j)) {
17 i++;
18 }
19
20 // If the end of s is reached before finding a match, return
21 // the number of remaining characters to append from t to s
22 if (i++ == lengthS) {
23 return lengthT - j;
24 }
25
26 // Move j forward to the next character in t
27 j++;
28 }
29
30 // If we reach here, all characters of t are matched in order within s,
31 // so there is no need to append any characters, hence return 0
32 return 0;
33 }
34}
35
1class Solution {
2public:
3 int appendCharacters(string s, string t) {
4 int m = s.size(); // Length of string s
5 int n = t.size(); // Length of string t
6
7 // Initialize pointers for strings s (i) and t (j)
8 for (int i = 0, j = 0; j < n; ++j) {
9 // Increment i until we find a matching character in s for t[j]
10 while (i < m && s[i] != t[j]) {
11 ++i;
12 }
13 // If we reach the end of s, return how many characters to append from t
14 if (i == m) {
15 return n - j;
16 }
17 // Move to the next character in s
18 i++;
19 }
20 // If all characters of t are found in s in order, no need to append any character
21 return 0;
22 }
23};
24
1function appendCharacters(s: string, t: string): number {
2 let m = s.length; // Length of string s
3 let n = t.length; // Length of string t
4
5 // Initialize pointers for strings s (i) and t (j)
6 let i = 0, j = 0;
7 while (j < n) {
8 // Increment i until we find a matching character in s for t[j]
9 while (i < m && s[i] !== t[j]) {
10 i++;
11 }
12 // If we reach the end of s, return how many characters to append from t
13 if (i === m) {
14 return n - j;
15 }
16 // Move to the next character in s and t
17 i++;
18 j++;
19 }
20 // If all characters of t are found in s in the given order, no need to append any character
21 return 0;
22}
23
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed by looking at the nested loops (represented implicitly through the sequential searches within the string s
):
- For each character in string
t
(n
characters total), the code potentially iterates through the entirety of strings
(m
characters) to find a matching character. - In the worst case, each character of
t
will be compared to each character ins
until a match is found or until the end ofs
is reached. - Therefore, the worst-case scenario would result in a time complexity of
O(m*n)
, wherem
is the length of the strings
andn
is the length of the stringt
.
Space Complexity
The space complexity of the code is quite straightforward:
- The code uses only a fixed number of variables (
m
,n
,i
, andj
) to keep track of the indices and lengths of the stringss
andt
. - No additional data structures are created that grow in size with the input.
- Thus, the space complexity is
O(1)
, which means it is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!