DP || Leetcode 5. Longest Palindromic Substring

Problem Link

In this problem, there will be given a string, we have to find the longest palindromic substring of this string.

For this purpose, we have to check all the substring we can generate. From them the longest one which is palindrome will be the answer. In the naive approach, surely will cross the time limit.

DP approach: Suppose we have a string "cababa". Lets simulate this string by building a table of 6*6.

The cell value (i,j) = 0, means starting from index i to index j of the string doesn't have a palindrome

The cell value (i,j) = 1, means starting from index i to index j of the string have a palindrome, and its size is (j-i+1)

1. A single character is a palindrome itself. so, we will fill all the diagonal(i,i) as 1. 

So, the table looks like Fig :1

                                           Fig[1]
2. We will check all of 2 size substring, they formed palindrome[if the string characters are same] or not.

    for (0,1)>> characters are 'c' and 'a' so its not a palindrome we will put 0 at (0,1) 

    for (1,2)>> characters are 'a' and 'b' so its not a palindrome we will put 0 at (1,2)

    for (2,3)>> characters are 'b' and 'a' so its not a palindrome we will put 0 at (2,3)

    ....

    ....

 

3.Then we will check if the start index i and the end index j is the same character. if they are same then we will check between them all the characters are palindrome or not. In other word mathematically we will say a range palindrome if and only if,
    s[i]==s[j] and table[i+1][j-1]==1

table[i+1][j-1] represents middle substring, if you dont catch it, you can understand this by doing some paper works.

Finally, our looks like Fig 2.

                                            Fig[2]

Code:

class Solution {
public:
    int dp[1000][1000];
    string longestPalindrome(string s) {
        int ans=1;
        int start=0,end=0;
        for(int i=0;i<(int)s.size();i++){
            dp[i][i] =1; 
        }
        for(int i=0;i<(int)s.size()-1;i++){
            if(s[i]==s[i+1]){ dp[i][i+1] = 1;ans = 2;start=i;end=i+1;}
            else dp[i][i+1] = 0;
        }
        
        for(int j=2;j<(int)s.size();j++){
            for(int i=0;i<(int)s.size()-2;i++){
                if(s[i]==s[j] && dp[i+1][j-1]==1){
                    dp[i][j] = 1;
                    ans = max(ans,j-i+1);
                    if(ans==j-i+1){
                        start = i;
                        end = j;
                    }
                }
            }
        }
        string ansString = "";
        for(int i=start;i<=end;i++){
            ansString.push_back(s[i]);
        }
        return ansString;
    }
};