Longest Palindromic Substring (#5 Leetcode)

This is one of the dynamic programming problems.

Palindrome is a string which reads the same in both directions.

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Naive Approach

The Bruteforce  solution will lead to O(N^3). 

1) To get all the substrings, it is O(N^2).

First character - "a", "aa", "aaa", "aaaa", "aaaab", "aaaabb", "aaaabba", "aaaabbaa"

Second character - "a", "aa", "aaa", "aaab", "aaabb", "aaabba", "aaabbaa"

And the list goes all the way through....

2) To check if the substring is palindrome or not, it is O(N). 

Because we will compare character by character having a pointer at the end and another at the beginning in linear time.

Dynamic Programming Approach

Instead of checking from the boundaries of the string, if we start from the middle and keep expanding to the left and right, it would be simpler. 

Step 1

First let's find if the string is palindrome or not for all the two sized characters. 

1. A single letter is always a palindrome, so I added 1 diagonally from top left to bottom right. 

2. Towards the left of the matrix, check if the two character string is palindrome or not in each iteration. 

As we are concerned about the palindromic string and only one string is given as input, it is sufficient to find the top diagonal half of the matrix values. 

        //Set Palindromic state for Single and Two sized Character
        for (int k = 0; k < len; k++) {
            dp[k][k] = true;
            if (k == len-1) {
                break;
            }
            dp[k][k+1] = (s[k] == s[k+1]);
        }

Step 2

Check the following conditions are true or not to fill the dp matrix 

1. s[i] equals s[j]. For example, string 'aabbaa' satisfies this condition. 

2. The next dp[i+1][j-1] is true

        //Set Palindromic state for all remaining characters
        for (int i = len-3; i>=0; --i) {
            for (int j = i+2; j < len; ++j) {
                dp[i][j] = (dp[i+1][j-1] && s[i] == s[j]);     
            }
        }

i = len - 3 would get you the last unfilled row for any given string length. 

j = i+2 would get us to the last unfilled column in the matrix.

After filling the table in the upper right triangle shape, the table look like this. 

Click here to view the whiteboard.

Step 3

Now, we will go through the matrix. We will consider only the cells with value true and if it is the new longest substring.

        //Find the longest palindromic substring
        int max = 0;
        string maxstr = "";
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if (dp[i][j] == true && (j-i+1 > max)){
                    max = j-i+1;
                    maxstr = s.substr(i,j-i+1);
                }
            }
        }

C++ Code

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) return "";
        int i = 0, j = 0;
        int len = s.size();
        
        //initialize dp[n][n], we only need half of dp
        bool dp[len][len];
        memset(dp, false, sizeof(dp));
        
        //Set Palindromic state for Single and Two sized Character
        for (int k = 0; k < len; k++) {
            dp[k][k] = true;
            if (k == len-1) {
                break;
            }
            dp[k][k+1] = (s[k] == s[k+1]);
        }
        //Set Palindromic state for all remaining characters
        for (int i = len-3; i>=0; --i) {
            for (int j = i+2; j < len; ++j) {
                dp[i][j] = (dp[i+1][j-1] && s[i] == s[j]);     
            }
        }
        //Find the longest palindromic substring
        int max = 0;
        string maxstr = "";
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if (dp[i][j] == true && (j-i+1 > max)){
                    max = j-i+1;
                    maxstr = s.substr(i,j-i+1);
                }
            }
        }
        return maxstr;
    }
};

Since vector of vectors decrease the performance, I just went with arrays. 

Instead of the two lines, 

        //initialize dp[n][n], we only need half of dp
        bool dp[len][len];
        memset(dp, false, sizeof(dp));

we can replace it with 

vector<vector<bool>> dp(len, vector<bool> (len,false));

Click here for Leetcode link