#define f(a,b) pair temp = func(s,a,b);if(temp.second-temp.first+1>ma){ma = temp.second- temp.first+1;x=temp.first;y=temp.second;} class Solution { public: pair func(string &s, int i, int j) { while(i>=0 && jma){f(i,i);} i=q+k; if(ima ){f(i,i+1);} if(min(2*i+1,2*(n-i-1)+1)>ma){f(i,i);} } return s.substr(x,y-x+1); } }; //Without DP : Runtime : 3s | Space : 7.1 MB //intuition : go thru every index and search for even palindrome and odd palindrome + maintain longest length so u dont have search in those subarrays which can't get upto maximum
@@wondersofmovies we are making a 2d dp table of vector of vectors where in the bracket the n signifies the number of rows and each col is also a vector of size n and we initialise al values with 0.
based on my analysis what I've come across is, if it's dp with string better try with tabulation itself rather than recursion ->memo ->tabulation. It will help you a lot in solving problem and building intuition. Thanks for the tutorial Alisha!!
I haven't even started DP as of now, but I was solving the Data Structures II of leetcode where I came across this question and now after understanding the concept you explained, it's so clear to me!!! Thank you so very much!!!!
Thank you so much. This video helped me a lot. Python version : n = len(s) dp = [[0]*n for j in range(n)] res = '' resLen = 0 for diff in range(n): for i in range(n): j = i + diff if j >= n: break if diff == 0: dp[i][j] = 1 elif diff == 1 and s[i] == s[j]: dp[i][j] = 2 elif s[i] == s[j] and dp[i+1][j-1]: dp[i][j] = dp[i+1][j-1] + 2 if dp[i][j]: curLen = j-i+1 if curLen > resLen: resLen = curLen res = s[i: j+1] return res
Great explaintion yet again, now addicted to your channels for explainations/logic😁 Tagging a **two pointer approach** for the same problem : 👇 class Solution { public: string longestPalindrome(string s) { int maxLengthOfPalindrome = 0; int maxStringStart = 0; int right , left; int lengthOfString = s.size(); int lengthOfPalindrome; string ans = ""; for(int i = 0 ; i < lengthOfString ; i++) { right = i; while(right < lengthOfString and s[i] == s[right]) right++; left = i - 1; while(left >= 0 and right < lengthOfString and s[left] == s[right] ) left--,right++; lengthOfPalindrome = right - left - 1; if(lengthOfPalindrome > maxLengthOfPalindrome) { maxLengthOfPalindrome = lengthOfPalindrome; ans = s.substr(left+1,maxLengthOfPalindrome); } } return ans; } };
understood everything didi.Keep up the good work😊😊.I have a suggestion in the code...instead of calculating substring again and again we can just keep track of start and end point of substring and then while returning we can return in subtring format using those indexes .it will reduce time complexity to calculate the substring here code for my explaination public String longestPalindrome(String s) { int n = s.length(); int dp[][] = new int[n][n]; int startIdx = 0; int endIdx = 0; int maxLength = 0; //diagonally iterating for(int diff=0;diff0){ if(j-i+1>maxLength){ startIdx = i; endIdx = j+1; maxLength = j-i+1;
just to add, check how substring method in ur language works. in some languages it takes length, in some others, it takes end index which can also be inclusive or exclusive. in java, use : substring(i, j+i) as it takes start index and end index where end is not inclusive. BTW, kudos for the explanation, couldn't be any simpler !
those who are facing problem in java code and thanks for such a great explanation 🙂 public String longestPalindrome(String s) { int n = s.length(); int dp[][] = new int[n][n]; int max = 0; String ans = ""; for(int diff = 0; diff len = 2-0+1 = 3 */ int len = j - i + 1; if(len>max){ max = len; ans = s.substring(i,j+1); // substring start from i and end at j so j+1 } } } } return ans; }
woow di ,such a great explanation,thanku for helping me ,i have read dp for the first time,but u explained each concept so well that i understood in go
I feel like i am really dumb. I understand the solution when i watch her video then don't remember it after some time . Its frustrating . Someone plz suggest some tips
its your video i search for when i search any Q because your teaching style is very easy to understand i had problem in understanding tabulation but your 1 solved Q made it clear which the whole playlist of others couldnt do
Mam I tried your approach in java on leetcode but only 12 out of 140 test cases has paassed. Can you help me find the error in the code. Code: class Solution { public String longestPalindrome(String s) { int n=s.length(); int[][] dp = new int[n][n]; String ans=""; int max=0; for(int diff=0;diff
The bug is ans=s.substring(i,max); is wrong. it should be ans=s.substring(i,j+1); Explanation: when we are updating the max it means we have the matrix indices which are nothing but string indices.
same goes with Aptitude Tests before interview rounds...may be they want to filter some students based on their logical and coding ability...BUT truth is this is not that much helpful in Development..
will you marry me? how come u so good with explanation and graceful? been following from so long❤ great, but please don’t post more and more problem just give core conepts in a single vide like nge, nse, bfs/dfs/disjointset/swapping technique etc
![Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]](http://i.ytimg.com/vi/DK5OKKbF6GI/mqdefault.jpg)
![Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]](/img/tr.png)
Code CPP:
int n =s.size() , maxlength = 0; string ans;
vectordp(n,vector(n,0));
for(int diff = 0;diff
#define f(a,b) pair temp = func(s,a,b);if(temp.second-temp.first+1>ma){ma = temp.second- temp.first+1;x=temp.first;y=temp.second;}
class Solution {
public:
pair func(string &s, int i, int j)
{
while(i>=0 && jma){f(i,i);}
i=q+k;
if(ima ){f(i,i+1);}
if(min(2*i+1,2*(n-i-1)+1)>ma){f(i,i);}
}
return s.substr(x,y-x+1);
}
};
//Without DP : Runtime : 3s | Space : 7.1 MB
//intuition : go thru every index and search for even palindrome and odd palindrome + maintain longest length so u dont have search in those subarrays which can't get upto maximum
Please first explain its recursive/memoized version then move to Bottom Up Approach
hi , im not able to understand this vectordp(n,vector(n,0)); can u pls explain this . im stuck in there 😢
Its says memory limit exceeded
@@wondersofmovies we are making a 2d dp table of vector of vectors where in the bracket the n signifies the number of rows and each col is also a vector of size n and we initialise al values with 0.
If possible make a playlist covering all DP concepts that would genuinely help because you teach very well.
+
same 100
++++++++
Yes your teaching strategy is really intuitive
+1
based on my analysis what I've come across is, if it's dp with string better try with tabulation itself rather than recursion ->memo ->tabulation. It will help you a lot in solving problem and building intuition. Thanks for the tutorial Alisha!!
I haven't even started DP as of now, but I was solving the Data Structures II of leetcode where I came across this question and now after understanding the concept you explained, it's so clear to me!!! Thank you so very much!!!!
Dry run and code explanation is just outstanding
Thank you so much. This video helped me a lot.
Python version :
n = len(s)
dp = [[0]*n for j in range(n)]
res = ''
resLen = 0
for diff in range(n):
for i in range(n):
j = i + diff
if j >= n:
break
if diff == 0:
dp[i][j] = 1
elif diff == 1 and s[i] == s[j]:
dp[i][j] = 2
elif s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = dp[i+1][j-1] + 2
if dp[i][j]:
curLen = j-i+1
if curLen > resLen:
resLen = curLen
res = s[i: j+1]
return res
Spent whole day on this , Thanks for each minute !
Your explanation is very smooth.
Thank You Alisha for this awesome video,
You explained complex things in a very easy manner,
May god bless You,
Keep it up
The way you explain its just another level every problem becomes easy.. 😇
Great explaintion yet again, now addicted to your channels for explainations/logic😁 Tagging a **two pointer approach** for the same problem : 👇 class Solution
{
public:
string longestPalindrome(string s)
{
int maxLengthOfPalindrome = 0;
int maxStringStart = 0;
int right , left;
int lengthOfString = s.size();
int lengthOfPalindrome;
string ans = "";
for(int i = 0 ; i < lengthOfString ; i++)
{
right = i;
while(right < lengthOfString and s[i] == s[right]) right++;
left = i - 1;
while(left >= 0 and right < lengthOfString and s[left] == s[right] ) left--,right++;
lengthOfPalindrome = right - left - 1;
if(lengthOfPalindrome > maxLengthOfPalindrome)
{
maxLengthOfPalindrome = lengthOfPalindrome;
ans = s.substr(left+1,maxLengthOfPalindrome);
}
}
return ans;
}
};
shouldnt that be +1
understood everything didi.Keep up the good work😊😊.I have a suggestion in the code...instead of calculating substring again and again we can just keep track of start and end point of substring and then while returning we can return in subtring format using those indexes .it will reduce time complexity to calculate the substring
here code for my explaination
public String longestPalindrome(String s) {
int n = s.length();
int dp[][] = new int[n][n];
int startIdx = 0;
int endIdx = 0;
int maxLength = 0;
//diagonally iterating
for(int diff=0;diff0){
if(j-i+1>maxLength){
startIdx = i;
endIdx = j+1;
maxLength = j-i+1;
}
}
}
}
return s.substring(startIdx,endIdx);
}
i have already done the question ....then also i came so that i can like ur video..thank for uploading video..keep going🤗🤗
simp
just to add, check how substring method in ur language works. in some languages it takes length, in some others, it takes end index which can also be inclusive or exclusive.
in java, use : substring(i, j+i) as it takes start index and end index where end is not inclusive.
BTW, kudos for the explanation, couldn't be any simpler !
those who are facing problem in java code and thanks for such a great explanation 🙂
public String longestPalindrome(String s) {
int n = s.length();
int dp[][] = new int[n][n]; int max = 0; String ans = "";
for(int diff = 0; diff len = 2-0+1 = 3
*/
int len = j - i + 1;
if(len>max){
max = len;
ans = s.substring(i,j+1); // substring start from i and end at j so j+1
}
}
}
}
return ans;
}
You are a great explainer Alisha.....Thanks for the video
Bhai kya hi samjhaya hai, sab samajh aa gya. Thanks for posting it. 🧡 from remote.
Iska Time Complexity ky rhega bro?
@@aakashbhandari9761 TC O(n2)
SC O(n2)
woow di ,such a great explanation,thanku for helping me ,i have read dp for the first time,but u explained each concept so well that i understood in go
Thanks a lot !! You made DP so easy ...I always found this so confusing until I came to your channel :) .
Your explanation is amazing. The suggestion is to cover some questions from GKG too. Thank you for nice content
Woww!!! That’s amazing!! So easy to understand!!
1000th like. I always search for your videos whenever I get stuck at any question. You are my tech crush❤
helpful👍
your energy of explanation way is incredible🥰...
The best explanation on YT..
Thankyou mam, Your teaching is amazing. Keep it up.
Hi were you learn from this all the stuffs and how you go through the problems and solve it can you exaplain
very well explained but I think little bit modification is required because it is not working for input (s="cbbd")
Thankyou alisha very informative tutorial
Thanku aman
Very amazing explanation!
your concept is very good.thanks .
The explanation is really great. Thanks for the video. But this is not Manacher's algorithm which can solve it in O(n). Do you have that explanation?
thanku ma'am for very clear explanation
such a great explanation, thanks
Best Explanation !
Awesome explanation
Loved your explanation please make more videos keep up the good work. If possible you can try to cover one of the DSA sheet of striver or love babbar.
Perfect explanation
Very well. Explained thnx a lot
This is very easy explanation for this question
Concise and Clear. Thanks
outstanding explanation mam ,i reallly loved it .......
great work alisha
Java code -:
class Solution {
public String longestPalindrome(String s) {
int end=s.length();
String ans="";
int maxLen=0;
int dp[][]=new int[end][end];
for(int arr[]:dp){
Arrays.fill(arr,0);
}
for(int diff=0;diff
Can we rename the variables i and j so that we can understand what those are even we look after years
Great Explanation !!
Great explanation. Period.
Nice explanation:)
Daymmmm, that was do much helpful. Thank you!
what about the remaining empty boxes in matrix? will not iterate?
alisha mam,
for this code time complexity o(n)?
Need explanation about recursive brute force approach then try to explain tabulation. Directly dive into tabulation will make confusion in DP.
Referred so many solutions but no help. Loved the fact how lemon squeezy you made this ques look like 😅😅😅😅
very very easy and helpful🔥🔥
I feel like i am really dumb. I understand the solution when i watch her video then don't remember it after some time . Its frustrating . Someone plz suggest some tips
nice explanation
Great explanation 😊😊
its your video i search for when i search any Q because your teaching style is very easy to understand i had problem in understanding tabulation but your 1 solved Q made it clear which the whole playlist of others couldnt do
Thanku🙏🙏🙏🙏
Best solution 👌
can you explicitly write the complexity also in every code
Absolutely perfect
Nice explanation 😊
It shows memory limit exceeded in interviewbit
which whiteboard application is used?
Nice Explanation . Is there any possibility that can you suggest any website for aptitude preparation and Guesstimate?
very well explained👏
great explanation
can you show non-dp approach for O(1)
Nice explanatuon
Amazing explanation
The method is not applicable to java..
Could you provide why it is?
Excellent
thanks
it helps a lot to understand ,Thank you so much for your contribution.but can we make it O(n) somehow??
Awesome 🤯👍
Time Limit Exceeded (TLE) error aa raha didi leetcode per ye code submit krne pe
Thank You!!
Great !
Great
mam baba is also plindrom substring so why it is not in ans?
No ! baba is not pallidrome when you read the string from back it will be abab which not equal to original one
@@aakashbhandari9761thank you for reply doubt clear
better than Nick
not able to understand this code
Your explanation is great but try going a bit slow to let it sink in for the viewers :)
Thank you
Have u studied chemistry from JMR sir in resonance.
thankyousomuchh
thanks girl
Amazing Explaination 🤩
Miss Alisha Kabhi apne dill mein bhi welcome kar lo hamesha youtube channel pe welcome karti ho 🙂🙂🙂
Genius
Mam I tried your approach in java on leetcode but only 12 out of 140 test cases has paassed. Can you help me find the error in the code.
Code:
class Solution {
public String longestPalindrome(String s) {
int n=s.length();
int[][] dp = new int[n][n];
String ans="";
int max=0;
for(int diff=0;diff
TRY THIS!!!
public String longestPalindrome(String s) {
int n=s.length();
int[][] dp=new int[n][n];
String ans="";
int maxlen=0;
for(int diff=0; diff
The bug is
ans=s.substring(i,max); is wrong.
it should be ans=s.substring(i,j+1);
Explanation: when we are updating the max it means we have the matrix indices which are nothing but string indices.
love you mam
Where r u @dhananjoy
why are u in so much hurry?
mujhe samaj nhi ata jab palindrome ,ye sb software development me kam nhi ata to padhate aur puchhte kyu h isse question
same goes with Aptitude Tests before interview rounds...may be they want to filter some students based on their logical and coding ability...BUT truth is this is not that much helpful in Development..
will you marry me? how come u so good with explanation and graceful?
been following from so long❤
great, but please don’t post more and more problem just give core conepts in a single vide like nge, nse, bfs/dfs/disjointset/swapping technique etc
I need ur another social media I'd need to talk with you i am not on LinkedIn i need to share some content to you .
Send here yr useful content
@@shimlamam6066 give me ur insta id
@@shimlamam6066 tomb tanane ka tlueprint dera hoga
Very Great Explanation 🔥