Append Characters to Strings to Make Subsequence - Leetcode 2486 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:26 - Coding Explanation

leetcode 2486

#neetcode #leetcode #python

[whoevenpaysforwinrar]

Shocked that this was a medium problem tbh

[simonvutov]

hehehe when you need him the most, he uploads

[maxmartin]

pointerT = 0
for pointerS in range(len(s)):
if pointerT < len(t) and t[pointerT] == s[pointerS]:
pointerT += 1
return (len(t) - pointerT)

[plsgivemecat]

3:24 "where do we put the d"
sorry. cool vid, thanks neetcode!

[jeet]

class Solution:
def appendCharacters(self, s: str, t: str) -> int:
i=0
j=0
while i<len(s) and j<len(t):
if s[i]==t[j]:
j=j+1
i=i+1
return(len(t)-j)

[JamesBond-mqpd]

My solution:

def appendCharacters(self, s: str, t: str) -> int:
k = 0

for i in range(len(s)):
if k < len(t) and s[i] == t[k]:
k += 1

return len(t) - k

[DeathSugar]

It's not O(s+t), but O(s), coz you need to check characters up to length s, and either t<=s and we have an early exit as best case, or we don't meet letter from t till the end of s, and calculate the rest in constant time.

[Dannnneh]

Simple approach with C++ std::string::find.
size_t i = 0, pos = 0;
while((pos = s.find(t[i], pos)) != std::string::npos){
++i; ++pos;}
return t.size()-i;

[harikrishnanb]

apart from leetcode, how to learn other technical skills?

[chrischika]

You dont need the else clause you always increase the i pointer

[asagiai]

*Haven't seen the solution yet.
I think I can you a queue here, especially on the second string.
Dequeue if a character in the queue is similar to the firsf string.
And maybe just return the remaining length of the queue.

Though this problem might have edge case I haven't accounted for., like letter position.

example if string 1 is leetcode and string 2 is neetcode. Because in this example you could just put 'n' after l or before l.
The return should be 1

In other note there are other valid solutions.

[christophersinger]

Would it not be simpler to iterate through s and increment a single pointer if there's a match? Like so,
class Solution:
def appendCharacters(self, s: str, t: str) -> int:
i = 0
length = len(t)
for c in s:
if i >= length:
return 0
if c == t[i]:
i += 1
return length - i

[pastori]

they need to hire someone just for the difficulties like how is this one medium

[sabukuna]

var appendCharacters = function(s, t) {
let j = 0;

for(let i = 0; i < s.length; i++){
if(s[i] == t[j]) j++
}

return t.length - j;
};

[fazalmohammad]

I saw subsequence and immediately went in direction of LCS but couldn't solve.

[MehmetDemir-xiyy]

I think time complexity is wrong. It should be O (min(s, t))

[asagiai]

On nevermind I forgot the append part.
leetcode and neetcode returns 8.

[ish]

class Solution:
def appendCharacters(self, s: str, t: str) -> int:

prev=-1
for i in range(len(t)):
fnd=False
for j in range(prev+1, len(s)):
if s[j]==t[i]:
prev=j
fnd=True
break
if not fnd:
return len(t)-i

return 0
What will be the time complexity of this code ?

[lokesh]

I feel embarrassed

class Solution {
public int appendCharacters(String s, String t) {
int prefix = 0;
int k = 0;
for(int i

int j = i+1;
k++;
while(k<t.length()){
boolean found = false;


j++;
found = true;
k++;
}
else j++;
}
if(!found){
break;
}
}
}
}
return t.length()-k;
}
}

[saranshthukral]

Uh oh Bambarding Linkedin requests now