Oh shit. It is possible to get O(1) space without modifying the input strings. Hint: go through strings in reverse. Full solution: leetcode.com/problems/backspace-string-compare/solution/

@dr.darkfurygaming9174

4 жыл бұрын

Hey I'm your daily viewer atleast you should give me heart 😇😇

@Errichto

4 жыл бұрын

@@dr.darkfurygaming9174 I gave you a like. Next time write something funny and more relevant to the video, then you might get a heart. That's the rules :D

@rockycooldude4889

4 жыл бұрын

yesssssssssssssssssssssssssssss....i beat you...i feel so fucking awesome...............................................i cant fucking believe it .........lol....it felt so obvious to go reverse(even though i know "obvious" is relative)........but ...that's what i was thinking while watching the video..why is he not thinking like this(but then i thought maybe i am stupid and there is a better way..xd...

@pskd73

4 жыл бұрын

I thought you would finish it in one minute. I took some 10 minutes. I feel satisfied. Anyways, I really like your videos. There are other people, who make videos for money or something else, but you, (y)

@justlola7402

4 жыл бұрын

Hey, I think we can go either forward (left to right) or reverse (right to left), seems going in reverse is easier

oh noooo, you really shaved it off and wont reveal yourself :((

Thank you for your videos Errichto. I enjoy watching you code and see how you think; it helps to improve my code.

I used a pointer approach. Have a pointer for both strings that goes from right to left. If it’s a #, then move left and keep track of how many #s were encountered and skip that many digits. Do the same for the other string. If the values are the same at both pointers, go left on both and keep repeating the process until the end. If they aren’t equal then exit out. At the end check that both pointers are -1 otherwise they are different strings.

@iiju8212

4 жыл бұрын

Would you like to share your solution? newbie here. A bit confused about your approach. Thanks.

@Aditya-us5gj

4 жыл бұрын

@@iiju8212 look at the first comment by Errichto. Always try your best to solve otherwise move to editorials. Don't ask for others solution buddy, editorials are best as they will do complexity analysis and will discuss all approaches.p

@shaypatrickcormac2765

4 жыл бұрын

yeah, i think everyone else use this approach. But Errichto always solving problems in counterintuitive way some how

@Errichto

4 жыл бұрын

@@shaypatrickcormac2765 Interesting opinion. On which of the previous 8 days did I use some unusual or counterintuitive approach?

@andreykarayvansky9549

4 жыл бұрын

@@shaypatrickcormac2765 using stack was actually the simplest approach. But it required extra memory. Most likely, since he is a competitive programmer it's natural for him to find to look for the simplest and known solution. Moving backwards has a tonne of corner cases.

Thank you do showing the whole think process and not jumping to the best solution result :)

Haha, looking at you struggle with this problem makes me feel much better about myself. There are problems that take me hours to solve, and you just need like 1-2 minutes to solve them, the feeling of watching you do it just makes me want to quit already, haha, but finally, I have the feeling that I'm faster than you, even just once, that's just great. You're the best. Thanks for the inspiration.

@AAAAAA-gj2di

2 жыл бұрын

Yup...sometimes I feel awesome if I notice few silly mistakes in his code before him

Well now you will probably get to 100k subs within minutes! We cannot stand the tension!

@uthamkanth2505

4 жыл бұрын

kruschiii The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)

First time I solved something faster than you without modifying the strings. Thanks for motivating.

hearing you think along helps. thanks for another one!

Really happy to see that you are actually a human! great video, keep it up!

@adarshkashyap8715

4 жыл бұрын

:p true

Finally, we found out you are still human. :)

I just got AlgoExpert with your coupon code, thanks for the help with your channel!

You can modify the input to satisfy the O(1) space complexity. I also modified the input string by removing the necessary characters and compared them. But even better solution i found in submissions after mine was accepted was using greedy approach. You just traverse through the backspaced characters and comparing only the relevant part at each recursion.

I like the fact that even if you are with excellent knowledge and skills you might still stuck at some point, when i do stuck at relatively easy problems i get sad tbh but this video motivated me, anyways i can’t wait for the face reveal 🙈🙈🙈

Yes.. I wait for your 100k... And advance congratulations for 100k 👏👏👏👏

@uthamkanth2505

4 жыл бұрын

Fuad Al Hasan The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)

I get so excited when I see a new errichto video!!! I love him so much lol

I just used while(s.size() > len) { s.pop_back(); } in the ending of the remove function to handle the remaining characters.

Great video, Can you please tell what device/tablet and application you use for the sketching part while explaining?

I used two stack . If I encounter a character then push it into the stack and if I encounter # then simply continue. Did it for both the strings and then compared both of them.

hey bro, can you help me with a problem? we are given n points we find manhatten distance between each pair. we are supposed to find the kth one.

Just iterate backward and keep count of # if count of #>0 then add character else continue repeat it for other string then compare at last

@Errichto bro I am a beginner in programming. Can you please share your journey how you became good at this competitive programming for ex: books you read, resources you used etc. Please make a video about how you started to learn so that I can take the path that you have gone through. Please make this video.

Can we use Rolling-Hash technique here for O(1) space, we can modify hash for each backspace by traversing back, and we will at most traverse each element twice.

Thanks again for this video! Can you confirm my thought? You wanted to get rid of the string creation because the size of that string increases as the input gets bigger and so that's a O(N) complexity, right? Thanks.

Hi @Errichto, which stopwatch do you use? Thanks!

Can we do it using stringbuffer where we can delete #character and a character before it using deleteAtchar method while wtraversing the entire string .if #character is the first character in the string S and T then just skit that iteration. At the end we can check ur the two modified string buffer using equal method and returning the same

Nic brother. I am learning to c first then i am going to c++ and then c#.Is thic plan nice or ok for me at first.

for some problems the solution button in the top right corner is not locked and it has some really good explanations

@360Anurag

4 жыл бұрын

Its locked only when the question is from premium content.

There is a function in C++ str.erase(index,no_of_characters); when you do this, it will erase the mentioned number of characters starting from that index. So I did str.erase(i-1,2) whenever I find str[i] =='#' And then i=i-2 because the next two characters index will in place of the removed ones. And Can't wait for the Face Reveal..although I know how you look! You really deserve more subscribers.

@manishbaghel3291

4 жыл бұрын

Yupp it was quite easy to write this way

@manishbaghel3291

4 жыл бұрын

​@@procoder6079 No the challenge was to do it in O(N ) time and O(1) space complexity and there was no such restriction for modifying the string.

@manishbaghel3291

4 жыл бұрын

@@procoder6079 ohh....yeah my bad in that case I guess traversing in reverse order is the only solution

@RajatSingh-dg8ov

4 жыл бұрын

Modified the string leetcode.com/problems/backspace-string-compare/discuss/572179/Easily-explained-and-0-ms-faster-than-100.00-of-C%2B%2B-submissions

@oisincarroll1171

4 жыл бұрын

std.erase is O(N), so your program is now O(N^2) though

why does if (ch==' ') give me an empty character constant if for example i replace hash with a space?? can anyone help please.

I modified the original string. 1) I ran a while loop till string is empty or i

why don't you just use .pop_back() for the modified solution. does that increase the memory?

I have been shouting - DO IT IN REVERSE lol

I was given this problem in a Microsoft onsite interview, first I was very happy since I proposed a stack solution in 10 seconds, however my interviewer told me to focus on O(1) approach, I struggled during the 40 min interview but I was able to find the solution by iterating backwards, however I was not able to complete my code :( , after checking realized this LC problems is marked as easy,

Hi, what's the timer plugin you were using? and what's the OS? Thanks.

@de_vamp

4 жыл бұрын

It's just cropped google stopwatch.

"Know my identity and so on" ... LOL

i used stack to solve this problem like push all the characters of the string . if we encounter a '#' then we pop the previous element.

@gitithkavitha8686

4 жыл бұрын

But then space isn’t O(1)

@ollpu

4 жыл бұрын

That's exactly the same as his first solution. Strings are like vectors are like stacks in C++.

I used a stack, although I feel that having a knack of solving questions using 2 pointer method is really useful

@doluadao1995

4 жыл бұрын

Well, you can use string as stack. It has pop() == pop_back() and push = push_back(). At the end you don't need to convert your stack to string.

@manavmohata1240

4 жыл бұрын

@@doluadao1995 you can just have 2 stacks and sompare them without converting them to strings

@manavmohata1240

4 жыл бұрын

@@doluadao1995 you can just have 2 stacks and compare them without converting them to strings

can't believe this is just a easy question

What's the app you use for the countdown clock? Is there an alternative for it in windows? :) Thanks for the videos Errichto!

@Errichto

4 жыл бұрын

It's just cropped google stopwatch.

No video, what did you do to your head ?

6:57 Here if you used 0x00 instead of '#' and for string comparison used strcmp if would've worked

Why aren't you participating in codejam round 1-A?

Don't be insecure because of the hair.. We all are here for your teachings:) please do videos as usual.

we want to see your new hair look.

Errichto...why do you like using the OOP format when programming?

@uthamkanth2505

4 жыл бұрын

William Tubbs The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)

This question took my 4 long hours !! Yet I was unable to pass one category of test cases. One more thing, in java, if I use StringBuffer( to convert my string to StringBuffer) to solve this, will it be treated as O(n) space ?

@arinroday302

4 жыл бұрын

You crazy bro. It's quite easy solution. Another way would be to iterate backwards from both Strings and skip a character if we reach a hash

@ishaangupta4125

4 жыл бұрын

It'll be O(n) space. Using a pointer approach would solve it in constant space

@ishaangupta4125

4 жыл бұрын

It'll be O(n) space. Using a pointer approach would solve it in constant space

@tkctko

4 жыл бұрын

StringBuffer creates another instance, which needs O(n) memory space. By the way, StringBuilder is faster than StringBuffer unless multi-thread is used.

@viraj_singh

4 жыл бұрын

Also, StringBuffer is faster than StringBuilder as StringBuffer is not thread safe

man i have never see this guy before, guy please sup :)

I use Stack technique for it

There is no eye contact that's so bad!

is it even possible? I did the same O(1) solution under 5 min

@errichto It seems you are really scared of your "head" space!

Till then, hair will be back.

🤟

Shaved my head and got a mohawk, show that shaved head to the world!

Was the haircut that bad 😆😂

At every accepted submission can you just give a dry run of the written code and explain each line of code by taking the example input?

I love how your avatar is sideways bro

One approach would be to go from last

@uthamkanth2505

4 жыл бұрын

Narayan Bhat The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)

This just demonstrates that Errichto is human :p

This problem was pretty hard (for an easy lol). I got the going through in reverse but had the issue where I was backspacing over backspace characters (e.g. abc#d##).

@ivanp4740

4 жыл бұрын

Haha, no it isn't )) I guess solving it with O(N) space it's really easy. So basic problem is easy O(N) it's just follow up, not the one you supposed to do as basic, so it shouldn't be an easy. I guess follow up is (medium-hard)

@hellowill

4 жыл бұрын

@@ivanp4740 yes the O(1) space

U can modify string they want from u don't use extra space

You can maybe use a picture of the teddy bear until 100,000 subscribers

Without changing the input: Solution: We can use 2 pointers each on both strings and start from the end of strings In a loop We compare characters if they are not # else we ignore as many characters as many # we encounter in each string Eventually if any string is traversed then we check that the other string will have any characters after removal of # or not

You definitely shaved yourself😂😂😂

face reveal? who don't you? ....... your work describes you..

Haircut went wrong? :-D

If u made a udemy course teaching essentials i would by it 10x

It took me a lot of time finally i used stack edit:- Your Channel logo already reveals your face lol

Face reveal 😂😂😂😂 bro u are too gud.

Hey I'm your daily viewer atleast you give me heart 😇😇

You can check the solution after submitting the answer. Its on the right hand side top

Haha your profile pic!!!! Revealed😍😍😍😍

In the codejam round 1 we need screencast with face pls😂😁

face reveal!!!!!!!! let's go

Haircut problems?

Did you just messed up your hair??😂😂😂

How is this problem tagged as easy xD.

really good problem if can't modify the strings

You sounds kinda different today. Hope everything is fine.

@Errichto

4 жыл бұрын

Maybe some subconscious thing like I talk louder when the camera is on :D or maybe this problem made me sad :D

What if the haircut is a diversion and the real issue is the disappearance of teddy 🤔🤔🤔

are you self taught programmer or school?

Why did you mess with your hair:(

So you are really human..😳

Here's how I solved mine by going through the string backwards: void process(std::string& s) { int n = s.length(); int skip = 0, actual = 0; for (int i = n - 1; i >= 0; --i) { if (s[i] == '#') { skip++; } else { if (skip == 0) { s[n - 1 - actual] = s[i]; actual++; } skip = std::max(0, skip - 1); } } s = s.substr(n - actual, actual); } bool backspaceCompare(std::string s, std::string t) { process(s); process(t); return s == t; }

@ianpan0102

4 жыл бұрын

Alternatively: void process(std::string& s) { int actual = 0; for (const auto& ch : s) { if (ch == '#') { actual = std::max(0, actual - 1); } else { s[actual] = ch; actual++; } } s = s.substr(0, actual); } bool backspaceCompare(std::string s, std::string t) { process(s); process(t); return s == t; }

rip hair

i did the problem by implementing stack.

@saurabh945644

4 жыл бұрын

That is not order 1 space.

@shashanktiwari4442

4 жыл бұрын

Well thats the worst solution u can have for this problem 😂

I modified the string and explained that here. leetcode.com/problems/backspace-string-compare/discuss/572179/Easily-explained-and-0-ms-faster-than-100.00-of-C%2B%2B-submissions

hard? the O(1) solution was the natural solution

My O(N), O(1) java solution paste.ofcode.org/yrbdPtrys2hcXURHpasnuP

well something goes wrong with shaving xd

Hair reveal tommorow

We already know what u look like

Face review at 100k.......................

1st comment

@classcure9769

4 жыл бұрын

so wht

subscribe to channel plsss...best line xD

@uthamkanth2505

4 жыл бұрын

d0ccy The concept is very well explained in this video infact i have my channel which has similar content.pls check, subscribe and show me your support if u like them and give me u r feedback in comment section.thank you:)

You shaved , didn't you? and now you are too embarrassed

This is my version github.com/pskd73/leetcode/blob/master/april_challange/p9.py

Hey I'm your daily viewer atleast you should give me heart 😇😇

public bool BackspaceCompare(string S, string T) { while (S.Contains("#")) { if (S.IndexOf("#") == 0) { S = S.Remove(S.IndexOf("#"), 1); } else { S = S.Remove(S.IndexOf("#") - 1, 2); } } while (T.Contains("#")) { if (T.IndexOf("#") == 0) { T = T.Remove(T.IndexOf("#"), 1); } else { T = T.Remove(T.IndexOf("#") - 1, 2); } } if(S == T) { return true; } return false; }