Time: 410 ms (35.25%), Space: 11.1 MB (60.87%) - LeetHub

JanaSabuj · JanaSabuj · commit 3a848c3e37be · 2022-08-09T22:15:39.000+05:30
diff --git a/5-longest-palindromic-substring/5-longest-palindromic-substring.cpp b/5-longest-palindromic-substring/5-longest-palindromic-substring.cpp
@@ -1,40 +1,50 @@
 class Solution {
 public:
-    pair<int,int> checkPal(int i, int j, int n, string& str) {
-        while(i >= 0 and j < n and str[i] == str[j]) {
-                i--,j++;
+    string longestPalindrome(string str) {
+        int n = str.size();
+        int dp[n][n];// dp[i][j] = 1 if str[i][j] is a palindrome
+                    //           = 0, otherwise
+
+        for(int i = 0; i < n; i++) {
+            for(int j = 0; j < n; j++) {
+                dp[i][j] = 0;
             }
-            i++,j--;
+        }
 
-            return {i,j};
-            // sz = max(sz, j - i + 1);
-    }
+        // 1 len
+        for(int i = 0; i < n; i++) {
+            dp[i][i] = 1;
+        }
 
-    string longestPalindrome(string str) {
-        int n = str.size();
-        int centers = 2*n - 1;
-        // * * * * * * * 
-        // 0   1   2   3
-        //     c
-        int sz = 0;
-        int l = -1, r = -1;
-        for(int c = 0; c < n; c++) {
-            // int i = c - 1, j = c + 1;
-            pair<int,int> p1 = checkPal(c-1,c+1,n, str);
-            pair<int, int> p2 = checkPal(c,c+1,n, str);
-            if((p1.second - p1.first + 1) >= sz) {
-                sz = (p1.second - p1.first + 1);
-                l = p1.first;
-                r = p1.second;
+        // 2 len
+        for(int i = 0; i < n-1; i++) {
+            dp[i][i+1] = (str[i] == str[i+1]) ? 1 : 0;
+        }
+
+        // >= 3 len
+        for(int l = 3; l <= n; l++) {
+            for(int i = 0; i < n - l + 1; i++) {
+                int j = i + l - 1;
+                // i-j
+                if(str[i] == str[j] && dp[i+1][j-1]){
+                    dp[i][j] = 1;
+                } else
+                    dp[i][j] = 0;
             }
+        }
 
-            if((p2.second - p2.first + 1) >= sz) {
-                sz = (p2.second - p2.first + 1);
-                l = p2.first;
-                r = p2.second;
+        // find lps
+        int sz = 0;
+        int start = 0;
+        for(int i = 0; i < n; i++) {
+            for(int j = 0; j < n; j++) {
+                if(dp[i][j] and (j-i+1) > sz) {
+                    sz = j - i + 1;
+                    start = i;
+                }
             }
         }
 
-        return str.substr(l, sz);
+        return str.substr(start, sz);
     }
 };
