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