#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.
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!!!!
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; } };
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; }
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;
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
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 !
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
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
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
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)
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
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 Alisha for this awesome video,
You explained complex things in a very easy manner,
May god bless You,
Keep it up
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
The way you explain its just another level every problem becomes easy.. 😇
Spent whole day on this , Thanks for each minute !
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;
}
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);
}
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
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 !
i have already done the question ....then also i came so that i can like ur video..thank for uploading video..keep going🤗🤗
simp
Your explanation is very smooth.
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
You are a great explainer Alisha.....Thanks for the video
1000th like. I always search for your videos whenever I get stuck at any question. You are my tech crush❤
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?
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
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
Need explanation about recursive brute force approach then try to explain tabulation. Directly dive into tabulation will make confusion in DP.
very well explained but I think little bit modification is required because it is not working for input (s="cbbd")
Hi were you learn from this all the stuffs and how you go through the problems and solve it can you exaplain
what about the remaining empty boxes in matrix? will not iterate?
Woww!!! That’s amazing!! So easy to understand!!
Best Explanation !
your energy of explanation way is incredible🥰...
thanks
alisha mam,
for this code time complexity o(n)?
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.
such a great explanation, thanks
helpful👍
Thankyou alisha very informative tutorial
Thanku aman
Excellent
Daymmmm, that was do much helpful. Thank you!
Thanku🙏🙏🙏🙏
thanku ma'am for very clear explanation
Thankyou mam, Your teaching is amazing. Keep it up.
The best explanation on YT..
your concept is very good.thanks .
This is very easy explanation for this question
Very amazing explanation!
Concise and Clear. Thanks
Very well. Explained thnx a lot
Can we rename the variables i and j so that we can understand what those are even we look after years
Nice Explanation . Is there any possibility that can you suggest any website for aptitude preparation and Guesstimate?
It shows memory limit exceeded in interviewbit
Great
not able to understand this code
can you explicitly write the complexity also in every code
Absolutely perfect
outstanding explanation mam ,i reallly loved it .......
Your explanation is great but try going a bit slow to let it sink in for the viewers :)
nice explanation
The method is not applicable to java..
Could you provide why it is?
Referred so many solutions but no help. Loved the fact how lemon squeezy you made this ques look like 😅😅😅😅
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
Perfect explanation
Great explanation. Period.
it helps a lot to understand ,Thank you so much for your contribution.but can we make it O(n) somehow??
which whiteboard application is used?
Thank You!!
Great Explanation !!
can you show non-dp approach for O(1)
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
great work alisha
Very Great Explanation 🔥
Awesome explanation
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
very very easy and helpful🔥🔥
Time Limit Exceeded (TLE) error aa raha didi leetcode per ye code submit krne pe
thankyousomuchh
Have u studied chemistry from JMR sir in resonance.
Great explanation 😊😊
Nice explanation:)
Best solution 👌
Thank you
Amazing explanation
love you mam
great explanation
Great !
Nice explanation 😊
thanks girl
Nice explanatuon
Awesome 🤯👍
Genius
why are u in so much hurry?
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.
Where r u @dhananjoy
Miss Alisha Kabhi apne dill mein bhi welcome kar lo hamesha youtube channel pe welcome karti ho 🙂🙂🙂
Amazing Explaination 🤩
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 well explained👏