5 Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

The idea:

• A trivial brute force approach would be to generate every substring O(n^2), and then return the one that both have maximum length and is palindromic, which will take total of O(n^3).

• A dynamic programming approach reduces this to O(n^2).

• We keep a boolean table that keeps track of every possible substring that will tell us whether or not a substring palindromic.

• Using dynamic programming, we but build bottom-down from the base case of one character, expand to 2 character, and so on and so forth.

• So first we fill out the trivial case (one character), of every possible substring e.g. banana = b a n a n a, which is always palindromic.

• Then the next case with 2 characters, which means we'll confirm that the characters are the same (definitionally the only way a 2 character word can be palindromic).

• Finally, every additional case 3 characters and up, we'll have to confirm two different things.

  • One, that first and last characters match (as we've added in the next level of substrings)

  • And two, that its previous substring is also palindromic (the substring that does not include the character we added). To check this, we refer to its previous position in the table, which will always be diagonally to the left.

• In the process, once we do find palindromic substring that exceeds the previous maximum, we update our max length as well as the iterators that follow.

Complexity: O(n^2) time and O(n^2) space where s the length of the string

string longestPalindrome(string &s) 
{
    /*
    cond 1: left and right most characters match
    cond 2: the substring with those characters stripped off is palindromic.
    */

    if (s.length() < 2) return s;

    const size_t size = s.length();
    vector<vector<bool>> dp_matrix(size, vector<bool>(size));

    // trivial case
    int max_len = 1;
    for (int i = 0; i < size; i++) {
        dp_matrix[i][i] = true;
    }

    // cond 1
    int left = 0, right = 1;
    int final_l, final_r;
    for (int i = 0; i < size - 1; i++) {
        if (s[left] == s[right]) {
            dp_matrix[left][right] = true;
            final_l = left;
            final_r = right;
            max_len = 2;
        }
        left++; right++;
    }

    // remainder case, size > 2
    left = 0, right = 2;
    int next = 2;
    for (int i = 0; i < size - 2; i++) {
        for (right; right < size;) {
            if (s[left] == s[right] && 
                dp_matrix[left + 1][right - 1]) {

                dp_matrix[left][right] = true;
                if (abs(left - right) + 1 > max_len) {
                    max_len = abs(left - right) + 1;
                    final_l = left;
                    final_r = right;
                }

            }
            left++;
            right++;
        }
        left = 0;
        right = left + ++next;
    }

    return s.substr(final_l, max_len);
}

int main()
{
    string test4 = "a";
    cout << longestPalindrome(test4) << endl;

    string test3 = "cbbd";
    cout << longestPalindrome(test3) << endl;

    string test = "banana";
    cout << longestPalindrome(test) << endl;

    string test2 = "babad";
    cout << longestPalindrome(test2) << endl;
}