Remove All Adjacent Duplicates in String II - Leetcode 1209 - Python
Vložit
- čas přidán 10. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/remove-...
0:00 - Read the problem
2:00 - Drawing Explanation
9:58 - Coding Explanation
leetcode 1209
#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Just got the news today that I'll be getting an offer from Amazon.
Thank you so much for all the effort you continue to put in this channel!
It really changes lives!
That's so great!! Congratulations 🎉🎉🎉
Can you please tell us about your preparation strategy in the discord channel for Neetcode?
Your vids are great, it's helped me progress to the point I can solve most mediums! I just solved this one before you uploaded (it is the daily challenge).
How long have you been practicing for?
Oh my gosh, this is incredibly intuitive. Push out what you can I love seeing these man!
I love you neet code 🤗 these videos are always a fantastic reference for when I am confused af. And huge respect for doing so much work for me by creating that website for me to track my blind 75 progress and you didn't even throw ads on it! I've got my first faang interview in just under two weeks and if I get it I attribute it 100% to your fantastic creations! Keep up the great work! I'm sure you will make it super far if you keep working as hard as you do!
more code nice
Wow, every time I watch Neetcode, I feel my brain refreshed! Thank you so much!
Nice explanation, I solved this on my own with a stack but you did it much cleaner and in a better way, thank you
Thanks! I didn't really know about stacks before but they seem really useful.
Also, thanks to you, I've managed to get the runtime down to 99ms by using a one-dimensional array as stack and other little things.
Amazing video! Very clear, thank you
Your explanation is simply amazing 😁
Your videos are awsome...Great Work...
always content as always neetcode! just a question though. wont you get in trouble if you make coding interview vids? i recall techlead got into trouble cuz of his youtube content with google
The best educational CZcams channel
The idea of combing value and count together is brilliant.🎉
You are amazing!!
Automatic like even before watching the entire video. Insane right ? Nah ... just complete confidence in the quality of your content. Hope you are feeling better now !!!
I thought of using stack, slowing building it one at a time keeping a top pointer and a start pointer(Star pointer and top are different only if there exists a continuous sequence of same chars) and use those pointers to remove continuous chars of Len k
Hi NeetCode,
Thank you for this great video. But speaking of final part of you solution.
In python string is immutable. So every time you use res += (char * count). It will not simply add char behind original string.
In fact it will create a new string object to achieve this += statement.
My question will be would it be more efficient to use a list to store all char by appending them and return "".join(res)?
Totally agree. I used ''.join([letter * count for letter, count in stack])
Appending to a string in python is an O(n+m) operation. The last loop looks O(n**2) to me.
so satisfying!
I feel a little accomplished if I were to solve the problem after the coding explanation without looking at your solution. Now all I need is to find the solution without looking at the explanation.
amazing !!!!
Hope you feel better soon
iA
I think that part when you creating res can be simplified to:
return ''.join([char * count for char, count in stack])
this is what i did. Makes it more efficient as well
I am not sure if this would be a valid test dataset: abcbbccaa.
If i am correct your explanation says that it would return "" in accordance of the stack a:3 b:3 c:3 though you can clearly see this string would return itself as leftovers.
How would we take this datapoint in account?
The stack is only tracking letters contiguously. For the string you posted the stack would look like:
a:2
c:2
b:2
c:1
b:1
a:1
neet as always!
Could you pls explain on how to do it if instead of adjacent same character, we have to remove if a pattern is repeated
Eg. Input - abcabcabcd
Output - abcd
Thanks
As soon as I saw the question, I knew it was similar to parenthesis problem. I wonder why this is medium difficulty, since it's very very similar to prenthesis problem.
I wish you learn Javascript and do the coding on Javascript :(
Would make a lot of people happy.
can we use hashmap keeping the chars as keys and values to n.o of occurences then remove all values as 3
Hashmap will not be able to check for “consecutive” K occurrences.
shout out to all loyal subscribers who were here before neet got into google👏🏿👏🏿👏🏿👏🏿👏🏿
beautiful
Requesting - 1910. Remove All Occurrences of a Substring
I come here to check the top LC question name and try to solve them myself in 40 mins. And see solution if I cannot.
not gonna lie, u were missed
If only u used c++. But anyways thanks for this amazing explanation
def remove_suplicates(string,k,last):
ans = ''
i = 0
while i
I believe the last line should be res = (char * count) + res since stack stores the chars in reverse order
no lol
You can see in the video that it passed the tests. If you poped characters from the stack you'd get them in reverse order but he just traverses the stack from the "bottom".
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
i = 0
length = len(s) - 1
while i < length:
if s[i:i+k] == s[i]*k:
s = s[:i] + s[i+k:]
i -= k
length -= k
i += 1
if i < 0:
i = 0
return s
This was my solution which passed all test cases. I was wondering what is the time complexity of this solution?? I think it is O(n^2) but could anyone give an example of the worst case when that would be correct?
your iterating about n times if searching in a string that its length decreases each time(given that u dont search from the start of the string), its like printing a pyramid of characters(each time you print a shorter string, if we condider printing 1 char O(1)) so still O(n^2)
also am new to the field but i dont know what you mean by wirst cade example, arent those of n solutions supposed to give us an idea about the performance and time of execution around infinity?
btw i thought of the exact same solution, and i forgot that k can get pretty big(took k as 3)so didint bother making a stack since the index needs only to go back 2 characters.
@@birdbeakbeardneck3617 ohh thanks understood.
isn’t it very similar to bubble sort’s time complexity?
@@VasheshJ yes
I think consecutive numbers are for example: 1, 2, 3, 4, 5, 6, so maybe 333 has a better name to call it?
Hi Your code is failing for K=1
this piece of code is giving Memory limit exceeded ,Can anyone please review this code
class Solution {
public:
string removeDuplicates(string s, int k) {
vectorst;
for(int i=0;i