Palindromic Substrings - Leetcode 647 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@jonaskhanwald566]

My day is incomplete without listening this: "Hey everyone, welcome back! and let's write some more neat code today".

[@algorithmo134]

Amazing explanation! Im really curious what jobs did you have previously and where?

[@lingyunsu1589]

Truly: "Hey everyone, welcome back! and let's write some more neat code today".

[@drstoneftw6084]

Shorter solution that I found class Solution: def countSubstrings(self, s: str) -> int: res = 0 def pl(l,r) -> int: if l < 0 or r > len(s) - 1: return 0 if s[l] == s[r]: return 1 + pl(l - 1, r + 1) return 0 for i in range(len(s)): res += pl(i,i) + pl(i,i+1) return res

[@seungjunlee00]

Currently completed around 40% of the BLIND list. Thanks neetcode for always very clear explaination!

[@srinadhp]

I owe you one for making this concept so simple and crystal!

[@richard12345789]

Bro dont stop posting videos, I will try to donate weekly for coffee and share link to atleast one person to support ur videos.

[@NeetCode]

Thanks, appreciate that a lot 😃

[@hwang1607]

After watching longest palindromic substring neetcode video came up with this: class Solution: def countSubstrings(self, s: str) -> int: res = 0 def check(l,r): nonlocal res while l>= 0 and r < len(s) and s[l] == s[r]: res += 1 l -= 1 r += 1 for i in range(len(s)): check(i,i) check(i, i+1) return res

[@americandream1989]

What a smart solution! I see this question is categorized as a DP problem on LC and was struggling of thinking to solve in a DP way. Really like the way you explain a question and find a much simpler way to solve it!

[@電腦騙徒剋星]

the dp is O n^2 and even easier lmfao

[@電腦騙徒剋星]

this can be solved in O n using weird string algo

[@indraxios]

loving blind 75 series, learning a lot

[@nehascorpion]

The best explanation on palindromic substrings so far! Thanks a ton!

[@kirillzlobin7135]

The clearest explanation all over the Internet

[@IslamWaleed-gg4mc]

14:06 what i did with 108 lines of code in cpp, he did in 16 lines of code in python

[@zaki_1337]

I was able to solve this today by myself because i'd seen you do it a couple of months back. Thanks for everything man!

[@dnm9931]

Keep making videos bro, you’re really good! thank you so much!

[@enkr1]

You can also use Manacher's algorithm for O(n) and O(n) time space complexity!

[@anusha3598]

thank you so much neetcode. It is such a relief that when i am stuck i know i can rely on you to help me out and understand something

[@mostinho7]

Great explanation but not sure why this is categorized as dp on your website Same solution as longest palindrome problem (for each index expand outwards to find palindromes)

[@johnnychang3456]

Beautiful and clean solution. Thank you. And I love your clean coding style!

[@MP-ny3ep]

Terrific explanation. So well explained.

[@alhdlakhfdqw]

really great in depth explanation thank you so much! :) subbed

[@NeetCode]

Happy it was helpful!

[@rentianxiang92]

as always, thank you very much for your hard work, you just making me one step closer to my new career

[@mdahadhossen6410]

Thlanks for smooth explanation

[@kautilyabhardwaj3400]

bestest teacher on youtube for leeeeeeeeeeeetcodeeeeeeeeee

[@Iamnoone56]

Saw this expand from center technique in longest palindromic substring question soln tab on leetcode it was not so clear but now its super clear and i learned how to use the technique

[@manishbolbanda9872]

this was very much intuitive, thanks for the video

[@CHUAN-CHI]

Thank you!

[@103himajapoluri6]

Very great solution without usage of dp

[@vincentlius1569]

Thanks man, my solution for this was Memory Limit Exceeded

[@shoooozzzz]

Top tier resource as I study algos for upcoming Google interview

[@NeetCode]

Thank you so much!

[@ChocolateMilk116]

thank you for explaining so clearly, this was really helpful

[@karamany9870]

Got this in an interview.

[@sancho7198]

google? :3

[@karamany9870]

Hackerrank OA for Goldman Sachs for new Grad.@@sancho7198

[@DhritiChawla]

Woah mind blown. Thank you for this explanation!!

[@sarthakjain1824]

Excellent explanation and code thank you so much

[@utkarshsharma1185]

Thanks for phenomenal explanation 👏

[@smartwork7098]

Beautiful solution.

[@gillesyvetot8269]

This is so well explained! You da real MVP

[@sweetpotatoeater3169]

This is absolutely beatuiful. Thank you sir!

[@darrylbrian]

Great video as per usual. I don't think it's necessary to pass in s into the countPalindromes helper function. It already has access to s and we're not changing anything to s when we pass it in.

[@jesusvzla5199]

do you know Manacher’s algorithm? you can achieve O(n) time complexity on this problem

[@RohanKumar-mh3pt]

perfect explanation

[@manojmpatil1269]

Beautiful explanation. Thank you!

[@CJ-ff1xq]

Quick question, why is this under the DP category? I don't see any DP in this solution?

[@mucle6]

If you go from the outside in you need dp. a substring from range 0-100 is a palindrome if s[0] == s[100] and 1-99 is a palindrome. 1-99 is a palindrome if s[1] == s[99] and 2-98 is a palindrome. checking the middle is repeated work that we can use dp to get rid of So you could optimize the outside in approach to use a 2d dp array to get it down to n^2 Btw this wasn't obvious to me. It took me 10 minutes to figure out why going outside in was slower than inside out

[@mohdalim77]

If the applied approach is Two Pointers then why it is listed in Dynamic Programming? I am new following Neetcode 75 please exlplain

[@kumarnishit6994]

there are many ways to solve a problem. DP solution is equally beautiful, but it has a lot of unnecessary space complexity.

[@rmiliming]

Thank you for your nice tutorial! Something seems a bit confusing to me and hopefully I can get some of your guidance! :) In the first while loop, would the res account for all single characters as palindromic substrings as well? Since l and r are both intialized as I and s[I]always = s[I] , which according to the line "res+=1", the res would be incremented by 1.

[@muralisriram8035]

Great Explanation! Thank you

[@namanvohra8262]

Thank you so much!

[@ruslanklymenko1019]

Could someone explain why its under 'dynamic programming' ? In my opinion proposed solution doesn't use this technique. Am i wrong?

[@dzianisdashkevich1848]

perfect explanation, thanks!

[@ChiCity511]

can we get a link to the spreadsheet with the descriptions please :)

[@IK-xk7ex]

I couldn't pass the test case #130 by this way, but all test cases from 1 to 129 passed :(

[@jayrathod9271]

Why the following approach is not working? class Solution: def countSubstrings(self, s: str) -> int: res = 0 n = len(s) #odd for i in range(n): l = i r = i while(l>=0 and r=0 and r

[@barnetthan9391]

instead of having if s[i]==s[r] be an if statement inside the while loop, make it another condition for the while loop to run: while (l>=0 and r

[@twhizzay]

In the brute force method, why is it n^2 substrings? In the 'aaab' example, I am only counting 10 substrings, not 16 (i.e. n^2 = 4^2 = 16).

[@johnnychang3456]

If you put it in code it would look like this: for i in range(len(s)): for j in range(i, len(s): subStr = s[i:j+1] print(subStr) You're right that it does not execute n^2 times, but I think in big O notation it is O(n^2).

[@kwaminaessuahmensah8920]

you’re a god

[@amitupadhyay6511]

is there any way we can use recursion with memoization for this question ?

[@Kumar08]

in "abc" why you didnt considered ab and bc as palindrome?

[@rohanvishayal8724]

Because ab != ba , same as bc != cb

[@lubdhakmahapatra8476]

@NeetCode: Can i have the Eth column of the google sheet in the starting of the video ?

[@jorgegonzaloalfaro5378]

thank you for this!!!

[@PanashePhotography]

great video

[@rathhen8384]

amazing video

[@papirreo]

I would tell the interviewer DRY code is not the end all be all. And then dry it.

[@marksaunders8430]

Hey man, thanks for the video. Do you mind posting your code in future videos? I probably miss something small and then the solution doesn't work so I spend a long time debugging it. Will appreciate it!

[@bhailog_gaming_2000]

Excellent

[@ameynaik2743]

Which tool do you use to draw out?

[@NeetCode]

I use Paint3D

[@braindeadcow7346]

Are you for real? My interviewer gave me 2 hints for 2d dp tf?

[@akshitmiglani5419]

How will this solution catch abba? I'm just curious.

[@blackwolf6687]

I see that the even Palindromes will catch that. starting at the first 'b', l=b and r=b

[@mahf7739]

awesome

[@vigneshsvsv]

Thanks for the solution. Is there any process that I can follow to think of a solution like this on my own?

[@sandypatel_]

why this qn in 1D dp?

[@rahatsshowcase8614]

nice

[@raylei4700]

Hi, I tried to use similar code to solve leetcode 516 longest palindrome subsequence(not substring). But got incorrect answers. Can you please explain how to solve it? my code is as follows max_len = 0 for i in range(len(s)): # odd case l, r = i, i cur_max = 0 while l >= 0: while r < len(s): if s[l] == s[r]: cur_max = cur_max + 1 if l == r else cur_max + 2 r += 1 break else: r += 1 l -= 1 max_len = max(max_len, cur_max) # similar for the even case

[@ShikshaMishraMTCS]

so are you still in google??

[@chehakmalhotra7807]

whys this DP

[@marksaunders8430]

Fails the test case "abccccdd"

[@marksaunders8430]

output is 15, expected is 7

[@rathhen8384]

@@marksaunders8430 single characters are palindrome so a,b,c,c,c,c,d,d should be 8 palindromes. Then cccc -> is 4 palindromes. Then dd which gives 15 total

[@adamsloma3850]

1000th like

[@richard12345789]

hi bro,Why dont u do twitch streaming+coding once a month

[@NeetCode]

Yeah, I do have plans for different kinds of videos and also live streaming, Q/A, etc. For the next month I'm gonna be pretty busy with life stuff, but after that I'm definitely gonna do some streaming

[@siddharthaarora4351]

wow?

[@naveenprasanthsa3749]

Hey u have already done this problem in Longest palindromic substring. Do more problems on data structures, graphs, job schedulings.

[@jorgegonzaloalfaro5378]

where are your manners smh.

[@omkarjadhav848]

Thank you for the great explanation.

[@rryann088]

beautifully explained! Thank you !!!