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