I knew from reading other explanations that it was the explanation itself that was hindering everyone including myself. You are so far the only person that actually explained how the dynamic approach works clearly.
What a great presentation and explanation ! You are just going frame by frame and bringing clarity all the way down deep! Keep doing such great videos for demystifying complex algos.
Thanks a million for making such an incredible explanation for a GFG code. Sometimes they have good codes, but no explanations or the explanations are not clear enough. This is just so well explained. All your videos are helping so many of us. Keep up the great work!
Thank you so much for the video! I hadn't truly understood the dynamic programming approach to the max palindrome substring problem until I watched your explanation. Thanks again!
Bro this is the best explanation for the question and I finally understood it. Explaining is an art and making others understand is a superpower and you clearly has it. The video was crisp and so easy to follow. Just loved it. Pls keep making more videos. I know you might be busy with other stuff(I am sure u might be working for some top notch company and if not then you are surely going to be very soon) but pls keep making more videos.
I really love how you draw and go through the DP table. I don't see many people explain it that way and it can be very hard to visual or trace through at first. Thanks So much!
good explanation! The reason this is a dp problem is that it has over lapping sub problems. For substring from index 1,5 we need to check if substr from index 2,4 is palindrome or not and for substr 0,6 we would not compute for substr 1,5. So it will take O(1) time instead of O(n).
Please, if possible, explain how you approach a problem and come up with solutions too as it'll help in developing our programming logic as well. Thanks for the great vids, keep em comin'! :)
wow this is gold. such a great solution. Thanks a ton. i usually approach dp problem with rec first then memoization then tabulaiton. bt this is more like concrete tabulation solutiion.
Java solution | DP thank you for the great explanation too :) 🔥 public String longestPalindrome(String s) { int n = s.length(); if (n == 1) return s; // dp[1][2] represents substring of s in range [1,2] inclusive is palindrome or not // 1 indicates palindrome in dp array and 0 represents not a palindrome int[][] dp = new int[n][n]; int start = 0, end = 0; // index of answer in s for (int i = 0; i < n; i++) { // start position in s // for upper triangular matrix for (int j = i; j >= 0; j--) { // end position in s if (i == j) dp[i][j] = 1; else if (i - j == 1) { // for substring of length 2 in upper traingular matrix if (s.charAt(i) == s.charAt(j)) dp[i][j] = 1; } // check border character and substring inside current border indicated by i and j else if (s.charAt(i) == s.charAt(j) && dp[i - 1][j + 1] == 1) { dp[i][j] = 1; } // tracking maximum length for substring with index in s if (dp[i][j] == 1 && i - j > end - start) { start = j; end = i; } } } return s.substring(start, end + 1); }
Thanks. Very useful. However, brute force can be done in O(n^2): for(0 through length of string-1) find the longest palindrome whose middle is in that position if(longer than the previous max) save the start and end indexes return substring at the saved start and end indexes
