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".

[@shoooozzzz]

Top tier resource as I study algos for upcoming Google interview

[@NeetCode]

Thank you so much!

[@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!

[@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

[@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 😃

[@nehascorpion]

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

[@IslamWaleed-gg4mc]

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

[@Varuns36]

loving blind 75 series, learning a lot

[@kirillzlobin7135]

The clearest explanation all over the Internet

[@johnnychang3456]

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

[@dnm9931]

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

[@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

[@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

[@MP-ny3ep]

Terrific explanation. So well explained.

[@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

[@alhdlakhfdqw]

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

[@NeetCode]

Happy it was helpful!

[@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!

[@enkr1]

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

[@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)

[@mdahadhossen6410]

Thlanks for smooth explanation

[@rentianxiang92]

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

[@CHUAN-CHI]

Thank you!

[@utkarshsharma1185]

Thanks for phenomenal explanation 👏

[@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.

[@manishbolbanda9872]

this was very much intuitive, thanks for the video

[@ChocolateMilk116]

thank you for explaining so clearly, this was really helpful

[@DhritiChawla]

Woah mind blown. Thank you for this explanation!!

[@ChiCity511]

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

[@sarthakjain1824]

Excellent explanation and code thank you so much

[@gillesyvetot8269]

This is so well explained! You da real MVP

[@manojmpatil1269]

Beautiful explanation. Thank you!

[@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

[@sweetpotatoeater3169]

This is absolutely beatuiful. Thank you sir!

[@sachinsudheer]

Could you make a video on the DP solution for this ?

[@muralisriram8035]

Great Explanation! Thank you

[@smartwork7098]

Beautiful solution.

[@lubdhakmahapatra8476]

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

[@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.

[@dzianisdashkevich1848]

perfect explanation, thanks!

[@amitupadhyay6511]

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

[@kautilyabhardwaj3400]

bestest teacher on youtube for leeeeeeeeeeeetcodeeeeeeeeee

[@vincentlius1569]

Thanks man, my solution for this was Memory Limit Exceeded

[@ameynaik2743]

Which tool do you use to draw out?

[@NeetCode]

I use Paint3D

[@hazelpham2404]

amazing video! thanks

[@karamany9870]

Got this in an interview.

[@sancho7198]

google? :3

[@karamany9870]

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

[@RohanKumar-mh3pt]

perfect explanation

[@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.

[@103himajapoluri6]

Very great solution without usage of dp

[@ruslanklymenko1019]

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

[@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).

[@namanvohra8262]

Thank you so much!

[@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!

[@sandypatel_]

why this qn in 1D dp?

[@Kumar08]

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

[@rohanvishayal8724]

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

[@jesusvzla5199]

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

[@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

[@jorgegonzaloalfaro5378]

thank you for this!!!

[@vigneshsvsv]

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

[@IK-xk7ex]

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

[@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

[@PanashePhotography]

great video

[@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

[@rathhen8384]

amazing video

[@bhailog_gaming_2000]

Excellent

[@ShikshaMishraMTCS]

so are you still in google??

[@papirreo]

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

[@kwaminaessuahmensah8920]

you’re a god

[@mahf7739]

awesome

[@chehakmalhotra7807]

whys this DP

[@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

[@rahatsshowcase8614]

nice

[@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

[@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 !!!