Your first statement made me crying for 2 hours straight
@nanda_83 жыл бұрын
lmao It broke my heart
@siddharthmagadum163 жыл бұрын
🥲
@ilanaizelman39932 жыл бұрын
Same!
@thatpanditcoder2 жыл бұрын
crying since 2 years straight
@primroseneog43022 жыл бұрын
true
@youssefmuhamad32134 жыл бұрын
I love your tutorials, how you go from the naive solution to the optimized one
@Errichto4 жыл бұрын
Thanks :)
@musafirgauravv4 жыл бұрын
I too liked his same approach, it helps the people who don't have the ability to see optimized solutions at the very beginning.
@aj97064 жыл бұрын
@@Errichto Given an array of integers,find the maximum value of a[i] - a[j] + a[k] with constraints I
@shashankmishra92384 жыл бұрын
@@aj9706 hi will seeing it as maximise ak-aj+ai and transversing i with j= i+1 and k=n-1 work?
@ashutoshmaheshwari8334 жыл бұрын
This is the beauty when someone red on codeforces solves interview problems. It was so easy for you Errichto, but for the sake of your audience you explained it thoroughly. Thanks :)
@harshitmittal12174 жыл бұрын
I just love how you go from the simplest to the most optimized solution and the way you explain the process for optimizing the code.
@BigFatSandwitch4 жыл бұрын
The small c++ optimizations you mentioned in this video will be really helpful for me while coding. Thanks for putting out content like these
@deDeca10004 жыл бұрын
This optimization isn't strict to c++. When we use &, it'll compute the 2 parts of operations independently of your logical value, when we use &&, it'll check the first part and if it's false the second part will not be computed because it'll be false anyway. The same works with || and |, when we use ||, if the first part is true, the second will not be computed because the operation will be true anyway.
@a.yashwanth3 жыл бұрын
@@deDeca1000 But this doesn't work in java.
@deDeca10003 жыл бұрын
@@a.yashwanth I guess it works too as a simple research that I did here.
@kruz29193 жыл бұрын
@@a.yashwanth Yes it works in Java since I kept the length check before the string check and my solution got accepted albeit with long runtime. Just one little manoeuvre to change the verdict from TLE to Accepted.
@harishgehlot__2 жыл бұрын
Thank you brother from another mother, everyone on KZbin showing the code of optimised approach, Only you showed the brute force
@kaiovieira2304 жыл бұрын
Love this! Because this is a simpler problem (comparing others in this channel) I could understand the proccess and I've got so many things to learn. Thank you!
@varunv66414 жыл бұрын
Wow, no ads in any video.... This man is a legend
@wedding_photography4 жыл бұрын
I wish you covered the Manacher's algorithm as well.
@techfornoobs42414 жыл бұрын
yes!
@ShreyanGoswami4 жыл бұрын
Thanks for the explanation. I came to watch your video after I solved the problem myself. I was not disappointed because you explored many options. For N^2 time complexity what I did was reversed the original string and used longest common substring between the original string and the reversed string. I got an edge case where it was finding strings of length 2 to be palindrome even if they were not.
@sanfarans4 жыл бұрын
My first thought was hashing. It's possible to hash the string and hash the reversed string. Then to find the longest palindrome, we can for every mid point (or double mid points for even length palindromes) iterate over it's prefixes and suffixes and compare them using hashes. Now add binary search and we don't have to do that for every pref/suf length and just for O(logn) of them. If I am not mistaken the total complexity would be O(n*logn)
@sanfarans4 жыл бұрын
On the other hand hashes can collide so it's kinda randomised. But still, risk is pretty low and can be further lowed by using pairs of hashes.
@Errichto4 жыл бұрын
You are completely right, and we can even get O(N) with hashes if we increment the answer by 1 instead of binary searching :) I just didn't want to talk about hashes in this video, too many things for a beginner's problem.
@damcism4 жыл бұрын
"we can for every mid point (or double mid points for even length palindromes) iterate over it's prefixes and suffixes and compare them using hashes." I don't understand this sentence. What do you mean by "it's prefixes"? By "it" do you mean "mid point"? If so, then what do you mean by a "prefix/suffix of a mid point"?
@praveenojha334 жыл бұрын
@@Errichto Can you please explain O(N) approach using hashes or can you give some reference to any blog or article where it is discussed ? I can only figure out O(NLogN) approach using hashes :(
@sanfarans4 жыл бұрын
@@praveenojha33 O(n) approach is Manacher's algorithm
@MrSun80804 жыл бұрын
Hi Errichto thank you for the video! I really appreciate your explanation on the problem that many users struggle. Do you mind if you could make more videos on the solution that are on the list from top 100 liked questions or top 100 interview questions that are more of a medium level from the LeetCode? this way I think more entry-medium level coders can enjoy your channel more instead of diving into your explanation on hard algorithmic questions (though I enjoy those too). Hope you can take this into a consideration! thank you always.
@MakoMako12343214 жыл бұрын
I'd love to watch O(n) solution from you, great video btw
@ritik846294 жыл бұрын
Yes indeed.
@МаксимЮрченков-ы5ь4 жыл бұрын
Notice that any palindromic substring is a common substring of s and rev(s). Now look at suffix structures in context of finding longest common substring.
@raushankumarraman72594 жыл бұрын
Your explanations of problems are awesome going from bruteforce approach to optimisation......
@achavan14 жыл бұрын
I really appreciate your videos. I think the intuition behind how you derive the solution is outstanding. Helps a lot to understand how you came develop an approach.
@dcodernz4 жыл бұрын
Great stuff, Errichto! There are far more successful KZbinrs with a greater following. BUT I think you're way ahead of them in terms of material and quality content. Would love to see more videos like this. I think at the moment you're far under rated. Keep up the good work! 😀
@muskanagarwal79374 жыл бұрын
I loved your way of breaking down the problem and gradually moving towards more optimized version. Would love your input on codechef problems from long challenge, cook off, lunchtime and various other categories of problem.
@CarrotCakeMake4 жыл бұрын
Loved it, good job. One small observation, the string "aaaaaa....aaaaa" is a degenerate case for time in your algorithm. Instead of iterating mid in 0, 1, 2, 3, 4, 5..... you could iterate mid in n/2, n/2 + 1, n/2 - 1, n/2 + 2, n/2 - 2, .... Then just check if mid is far enough away from the edges to make a possible new best. That puts you really close to O(n) .
@Errichto4 жыл бұрын
Sure, but then there can for sure be something similar to aaa...aa that will still be slower. It just shows that a problem author has a hard job of creating good tests :D
@atibhiagrawal64604 жыл бұрын
Thank you so much for these Leetcode tutorials. Absoultely love them !
@RaGa_BABA3 жыл бұрын
errichto makes me wanna leave programming and love programming at a same time..
@Akshaykumar-bl8ok2 жыл бұрын
One Errichto video teach you a lot of extra things along with the actual solution.
@mfaraday40444 жыл бұрын
Mindblowing sir . Thankyou very much . Your way of explaination is unique.
@Laeyz4 жыл бұрын
you really made me question my understanding of binary search.I didn't get that n^2logn approach. Edit: i get it now , thanks.
@devendrasingh47764 жыл бұрын
Tell me bro what you understand please . 😢😢
@Laeyz4 жыл бұрын
@@devendrasingh4776 normally you search for a value in array or something but in this he was trying different answers in binary search way, it was long ago so i dont remember much.
@devendrasingh47764 жыл бұрын
@@Laeyz but why he did even odd thing
@AmanDeep-fp9ui4 жыл бұрын
Personal opinion but I would always go O(nlogn) with hashing and binary search. Its more intuitive than manacher algorithm and has just a logn extra factor.
@chongluo34904 жыл бұрын
Wow, your tutorial is so cool, it gives me a more general solution for optimization which could be applied to other Leetcode problems.
@arghyadeepmandal4458 Жыл бұрын
Came here for Manacher's but learnt a lot of new things 🙂.Beauty😎
@shahriardhruvo43332 жыл бұрын
You are awesooome, thank you. I love that you first write the naive solution and then explain and improve the code bit by bit :3
@MakoMako12343214 жыл бұрын
Why this two loops (odd/even length) are one after another? Why aren't they used based on length of string? Why it doesn't break when break when used on odd length string? (because in this case part of algorithm for odd is used first, and then part for even length is used on odd length) Why isn't it a problem? edit: Also why after using only one loop (for even or odd) this is not working properly? edit2: Ok, now I (probably) understand. One loop is for finding odd length palindrome (not odd length input), and other is for even length palindrome (not even length input). Am I right now?
@prathamnishad10334 жыл бұрын
on average how many problems you solve in a day (now and in the past). and Do you recommend sticking to a problem even when you cant get you head around it for days or leave it and look at the solution(or hint).
@davidalexandru78484 жыл бұрын
ive just replied to get notification for answer
@prathamnishad10334 жыл бұрын
@@davidalexandru7848 welcome
@EdinssonMelo4 жыл бұрын
Thx for the tutorial. I would appreciate it if you continue to share well known topics.
@lequocthinh89923 жыл бұрын
The C++ optimization's rly helpful
@hardikprajapati6714 жыл бұрын
Can you please give us tutorial on Manacher's Algorithm !! i didn't understand well i have seen lots of video on Manacher's Algo!! you teaches very well!!
@GDGET723 жыл бұрын
Hi @Errichto, I'm wondering how making change to parameter type: (string s) -> (const string& s) would let a for loop exit with early condition hence faster-than-linear runtime. @5:58. Do you mean such change is coming from the algorithmic change and changing the paramter type would only save CPU from using extra memory to take in s? or is there something special about how for loop treats a reference ? Thanks for your time in advance
@fbru024 жыл бұрын
Excellent video !! need to bring back the second errichto
@035asadali82 жыл бұрын
damn amazing i just did this question today but your dynamic programming solution is faster than mine, amazing
@ambersinghrok4 жыл бұрын
This is the best explaination i have heard so far...plzzz me lots of videos it will be helpful for my upcoming interviews.
@Zzznmop4 жыл бұрын
thank you for the lovely 25 minute explanation even though i know you can do this in 25 seconds. you are truly a gift to us all who enjoy competitive programming. p.s. i finally solved my first problem solved in under 5 minutes during a 3-problem online assessment, and boy did it feel amazing! Too bad the other two took about an hour each because i got ahead of myself after the first solution :P
@Dennis-Ong3 жыл бұрын
The high is amazing when you solve a (relative difficult ) problem. The low is terrible when you trying to understand a solution or freeze in interview.
@yogeshvishnole12643 жыл бұрын
Not able to understand the second solution in which you use the parity can you explain it with some diagrams. Thanks for sush easy explanations.
@singh.guranshАй бұрын
Great explanation Errichto! Loved it! ❤
@mahesh42744 жыл бұрын
Thank you for the explanation..... Hoping you will make more tutorials for beginner's like me...
@Errichto4 жыл бұрын
So, something at this level or easier?
@mahesh42744 жыл бұрын
@@Errichto same level, also tips on data structures/algo if possible. You know like how to approach the problems with specific ds. Thanks for the reply.
@kaiovieira2304 жыл бұрын
For me, something at this level is great! But easier things would be awesome too
@minciNashu2 жыл бұрын
string substr allocates a new string. string_view, span or plain pairs of pointers should be used in examples like this, for constant time.
@Xyvier4 жыл бұрын
This is so informative and awesome!
@Errichto4 жыл бұрын
Thank you :)
@MrWolfgangWeiss4 жыл бұрын
What software do you use to record yourself and screen on Ubuntu? Well done by the way.
@yugioh88104 жыл бұрын
I didn't understand the parity part, can anybody elaborate on that ?
@huan80363 жыл бұрын
As Errichto pointed out, using a palindrome, we can have a sub palindrome by removing two outermost value. The sub palindrome has the same parity as the original palindrome (the longer one). It's a fact that a palindrome with EVEN length can only have sub palindromes with EVEN length. The same thing happens to palindromes with ODD length - their sub palindromes must have ODD length too. Therefore, if we found a palindrome which has an EVEN length, the possible longer palindrome derived from it must have an EVEN length too (i.e they have the SAME parity). The parity part of Enrichto algorithm is to make sure we only looking for length that are worth checking. E.g. If we want to check if there's a palidrome with EVEN length, we will only look for EVEN length cases. The binary search really helps this idea to happen in O(logN); but we can implement it in O(N) just by looping through the string with the index increase by 2 each loop Hope this helps
@somesome13153 жыл бұрын
parity is for checking the length of best_s is whether odd or even
@anonymoussloth66873 жыл бұрын
@@huan8036 Can you explain a bit more of how binary search is even used here? I understand the even and odd length logic of the palindrome. But how and why Binary search is used in this is still not clear
@akshobhya_86904 жыл бұрын
It is the best video I've ever seen for this problem. Your approach is awesome dude.
@Gaurav-mq8yp10 ай бұрын
Can you please make a video on Manacher's Algorithm Errichto?
@danieltannor66474 жыл бұрын
Thanks for your explanation! A quick note: @19:04, I don't think it's N positions, but rather 2N-1 positions (because middles can be spaces between characters)
@kenjiaoki98973 жыл бұрын
Could someone kindly refer me to some material explaining the use of parity in Binary search? I did not exactly understand what @Errichto was trying to do there.
@yogendrapratapsingh76183 жыл бұрын
yeah ..me too
@RohanKumar-zn4qg4 жыл бұрын
Hello Errichto...Kindly upload videos on greedy strategy...I have solved more than 100 Div2C problems...yet whenever a greedy comes even in B ,I cant figure out whether greedy will work or not...or to which variable I should do greedy on.
@jeizart69824 жыл бұрын
watching you makes me think of quitting my job
@mahesh42744 жыл бұрын
Can you make a video on how to get started in programming and also competitive programming, from zero to hero, how to reach at your level???
@vivekchoudhary87454 жыл бұрын
Goto any coding platform I prefer leetcode, select the difficulty to easy initially. First and foremost, make a habit of solving problem by thinking out loud, marker and board or pen and paper, DO use it, I repeat, USE MARKER AND BOARD OR PAPER AND PEN BEFORE EVEN LAYING YOUR HANDS ON THE KEYBOARD. Work our the problem slowly. This is the key. I used to jump straight to keyboard when I started doing competitive coding. Using the pen and paper beforehand to workout the problems (the process) builds problem solving networks in your head. Good luck! Don't give up!!
@mahesh42744 жыл бұрын
@@vivekchoudhary8745 thanks for the big reply, I will try to make a habit of pen n paper and practice.
@vivekchoudhary87454 жыл бұрын
@@mahesh4274 I'd be super glad if I could help others, also, as you progress further you will realize that there are different domains of problems, like graph problems, string related problems, array, tree or hash etc. try to find the out which part is your weakest work on it. fight onn!!
@rishabhb26884 жыл бұрын
Look at the Getting Started section in his github repo. If you want a good book download competitive programmer's handbook and practise codeforces, USACO, ACM problems, if youre prepping for olympiads, if for an interview, do some leetcode too.
@mahesh42744 жыл бұрын
@@vivekchoudhary8745 I just started programming, but I will try to help if I can, I will try to create a blog or youtube channel to share knowledge..
@nurjamil63813 жыл бұрын
love ur videos bro, didnt quite understand in binary search part tho, maybe with a little bit more replay i can understand it, thank you for the video!
@jonty35514 жыл бұрын
Hoped u would have covered manarch's algorithm as well!!!!
@mechashadowx4 жыл бұрын
helpful details, that was amazing
@mesh4752 жыл бұрын
You are very smart. Great explanation
@mukulkumar23164 жыл бұрын
plz make a video on greedy problems, i just don't know how to go about it.. always loved ur channel , thanks in advance
@happyhappyguy50344 жыл бұрын
I don't understand the binary search one. Why do we need to consider parity?
@Errichto4 жыл бұрын
Because maybe there is a palindrome of length 6 but not of length 5. So what happens if you ask "can answer be 5?" in binary search and it turns out it can't? You will now search for answer between 1 and 4.
@happyhappyguy50344 жыл бұрын
@@Errichto thank you for replying, I understood it completely wrongly previously so I was very confused. But now I completely understand the solution.. :D This is very helpful btw!
@techgamer13334 жыл бұрын
Need More Videos Like this
@CarrotCakeMake4 жыл бұрын
I thought of a content suggestion, some of the "hacking" rules sound fun. It might be cool to make a video where you go through some of the winner's submissions and try to find counter examples for them. I think it wouldn't be rude if you only went after the winners, or maybe if you are friends with any of them ask them if they mind.
@Errichto4 жыл бұрын
They don't often submit incorrect ideas ;p strong participants have good intuition and they can prove their solution. It would be much easier to look through their wrong submissions though, but maybe I will just discuss my own mistakes?
@CarrotCakeMake4 жыл бұрын
@@Errichto We don't make mistakes, we just have happy accidents!
@mathiaspresthagen49214 жыл бұрын
I am currently through to the national finals of the informatics olympiad, but I'm not sure how to practice for it. Any tips or ideas?
@RAP4EVERMRC962 жыл бұрын
06:08 why does comparing by reference is faster than comparing two string variables?
@rkalyankumar Жыл бұрын
I still didn't understand parity and binary search based solution to this problem. Any good materials for this to read & analyse?
@cojocarucosmin2024 жыл бұрын
U r such a good teacher bro
@clivefernandes54354 жыл бұрын
Hey can u suggest a book for solving problems using methods like the monarch think u talked abt
@subrintakarmakar54363 жыл бұрын
Thanks this is faster than normal dp
@paragroy53594 жыл бұрын
Sir,it was really good.
@pyak67613 жыл бұрын
lol i come after struggling like hell: "quite an easy problem" me: ded. "...if you have competitive programming experience", me: oh phew, nope just a job that has nothing to do with LC.
@sagarnikam60594 жыл бұрын
In contests like codejam and kickstart how often we need to check our program by writing brute force solution and finding cases where our optimal solution is giving WA... Have you used this method of checking programs in short contests also..
@Errichto4 жыл бұрын
Codejam and Kickstart have feedback for small constraints so it isn't that important. Maybe useful if you want to find that countertest.
@kashireddydurgadevi79983 жыл бұрын
Helpful information thankyou
@ajeetworking4 жыл бұрын
I got the first for-loop...it takes every element and expands towards the right and left side to get the largest palindrome...but can anyone explain the purpose of the second for loop?.
@adityamondal11364 жыл бұрын
Sir I Would request you to post a solution for CodeForces Contest 615 Div.2 Problem 1 I really loved the video
@Quassar183 жыл бұрын
Funny thing: if you implement this solution in Swift language, it won't be accepted due to exceeded time. Test case has 1000 "a" chars string. I guess the only option is to go with a suffix tree then.
@hussainrizvi18873 жыл бұрын
Can someone explain the const string& trick to me again? Isn't the reverse() still O(N)?
@RG-sl6ix4 жыл бұрын
Is there any algorithm, that could be a efficient replacement for Longest Common Substring with k-mismatches
@chienglsictfried18583 жыл бұрын
yes
@RG-sl6ix3 жыл бұрын
@@chienglsictfried1858 and that will be???
@yuvarajanm20593 жыл бұрын
Can anyone tell in the binary search method why we change the low and high value if it is not match with parity and we also increase the mid value if it is not match with parity instead of that can we only modify the mid value if it is not match with the parity.. Please correct me if i am wrong.
@sivaan70562 жыл бұрын
Never thought of binary search 🥺
@bharath43974 жыл бұрын
really good explaination
@cluutech83633 жыл бұрын
@8:20 Binary search explanation
@faiz6974 жыл бұрын
I'm doing this problem for the last 20 mins, and it seems that the test case no 26('abb') is giving me the wrong result. When I checked it by inputting the input in the test case, it's giving me the correct answer. Anyone can explain to me why is it happening?
@nikhilrana88003 жыл бұрын
Can anyone please explain why we add 1 in the mid-x+1? I am not able to figure it out.
@surajbisa29414 жыл бұрын
thanks a lot your great work!
@anonymoussloth66873 жыл бұрын
can someone explain the n2logn solution in detail. How is Binary search used here?
@abhishekk.39774 жыл бұрын
It's 02:33 AM and holy Jesus why tf I couldn't get past the first approach. ^_^
@bhavanprajapati47734 жыл бұрын
Please explain O(N) solution
@ritik846294 жыл бұрын
What does the parity means in this video?
@rasecbadguy56004 жыл бұрын
How to solve this problem using suffix array?
@ivanleon61643 жыл бұрын
you are a hero!
@sairohit82013 жыл бұрын
guys , what does this mean i'm seeing this for the first time for(int parity: {0,1} ) { } is this a cpp thing?
@vishalyadav72454 жыл бұрын
Great tutorial
@ankitrookies23573 жыл бұрын
nice explanation
@prabhudeengautam18454 жыл бұрын
nice explanation!
@setukumarbasak67294 жыл бұрын
Can anyone explain in details about the parity logic?
@unstable_diffusion4 жыл бұрын
hackers hate to mess with this guy
@nikhilkumar-ot9rn4 жыл бұрын
could u please once more explain that parity thing ..please!!!!!!!!!
@ankitrookies23573 жыл бұрын
good explation
@huuarethey4 жыл бұрын
ah yes the most masterful power nerd
@peterg69532 жыл бұрын
Lol no way I'd figure this out in a technical interview if I didn't study it.
@shashankmishra92384 жыл бұрын
I thought you will solve by manacher's algorithm
@mohitsingh7793 Жыл бұрын
No need to write O(n2) code twice : Approach: Consider every index as a center/mid,expand around the center to find the pallindrome.Mark the empty spaces as '# or any special character.Basically it has done for the even length string. string longestPalindrome(string s) { int n=s.size(); string res; res+='#'; for(int i=0;i
@justinUoL3 жыл бұрын
the appropriate playpack speed is advised to be 0.5