Longest Palindromic Substring Solutions in C++

// Source : https://oj.leetcode.com/problems/longest-palindromic-substring/
// Author : Hao Chen
// Date   : 2014-07-17



#include <string.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string findPalindrome(string s, int left, int right)
{
    int n = s.size();
    int l = left;
    int r = right;
    while (left>=0 && right<=n-1 && s[left] == s[right]) {
        left--;
        right++;
    }
    return s.substr(left+1, right-left-1);
}


// This is the common solution.
// Actuatlly it's faster than DP solution under Leetcode's test
// the below optimized DP solution need 700ms+, this needs around 250ms.
string longestPalindrome_recursive_way(string s) {
    int n = s.size();
    if (n<=1) return s;

    string longest;
    
    string str;
    for (int i=0; i<n-1; i++) {
        str = findPalindrome(s, i, i);
        if (str.size() > longest.size()){
            longest = str;
        } 
        str = findPalindrome(s, i, i+1);
        if (str.size() > longest.size()){
            longest = str;
        } 
    }

    return longest; 
}

//================================================================================


void findPalindrome(string s, int left, int right, int& start, int& len)
{
    int n = s.size();
    int l = left;
    int r = right;
    while (left>=0 && right<=n-1 && s[left] == s[right]) {
        left--;
        right++;
    }
    if (right-left-1 > len){
        len = right-left-1;
        start = left+1;
    }
}

//The following solution is better than previous solution.
//Because it remove the sub-string return in findPalindrome().
string longestPalindrome_recursive_way2(string s) {
    int n = s.size();
    if (n<=1) return s;

    int start=0, len=0; 
    string longest;

    string str;
    for (int i=0; i<n-1; i++) {
        findPalindrome(s, i, i, start, len);
        findPalindrome(s, i, i+1, start, len);
    }

    return s.substr(start, len);
}

//================================================================================

// Time/Memory Limit Exceeded
string longestPalindrome_dp_way(string s) {

    string longest;

    int n = s.size();
    if (n<=1) return s;
    
    //Construct a matrix, and consdier matrix[i][j] as s[i] -> s[j] is Palindrome or not.

    //using char or int could cause the `Memory Limit Error`
    //vector< vector<char> > matrix (n, vector<char>(n));

    //using bool type could cause the `Time Limit Error`
    vector< vector<bool> > matrix (n, vector<bool>(n));

    // Dynamic Programming 
    //   1) if i == j, then matrix[i][j] = true;
    //   2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i+1][j-1])
    for (int i=n-1; i>=0; i--){
        for (int j=i; j<n; j++){
            // The following if statement can be broken to 
            //   1) i==j, matrix[i][j] = true
            //   2) the length from i to j is 2 or 3, then, check s[i] == s[j]
            //   3) the length from i to j > 3, then, check s[i]==s[j] && matrix[i+1][j-1]
            if ( i==j || (s[i]==s[j] && (j-i<2 || matrix[i+1][j-1]) ) )  {
                matrix[i][j] = true;
                if (longest.size() < j-i+1){
                    longest = s.substr(i, j-i+1);
                }
            }
        }
    }

    return longest;
}

// Optimized DP soltuion can be accepted by LeetCode.
string longestPalindrome_dp_opt_way(string s) {

    int n = s.size();
    if (n<=1) return s;

    //Construct a matrix, and consdier matrix[j][i] as s[i] -> s[j] is Palindrome or not.
    //                                 ------^^^^^^
    //                                 NOTE: it's [j][i] not [i][j]

    //Using vector  could cause the `Time Limit Error`
    //So, use the native array
    bool **matrix  = (bool**)malloc(n*sizeof(bool*));
    int start=0, len=0;
    // Dynamic Programming
    //   1) if i == j, then matrix[i][j] = true;
    //   2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i-1][j+1])
    for (int i=0; i<n; i++){
        matrix[i] = (bool*)malloc((i+1)*sizeof(bool));
        memset(matrix[i], false, (i+1)*sizeof(bool));
        matrix[i][i]=true;
        for (int j=0; j<=i; j++){
            // The following if statement can be broken to
            //   1) j==i, matrix[i][j] = true
            //   2) the length from j to i is 2 or 3, then, check s[i] == s[j]
            //   3) the length from j to i > 3, then, check s[i]==s[j] && matrix[i-1][j+1]
            if ( i==j || (s[j]==s[i] && (i-j<2 || matrix[i-1][j+1]) ) )  {
                matrix[i][j] = true;
                if (len < i-j+1){
                    start = j;
                    len = i-j+1;
                }
            }
        }
    }

    for (int i=0; i<n; i++) { 
        free (matrix[i]);
    }
    free(matrix);

    return s.substr(start, len);
}


string longestPalindrome(string s) {
    return longestPalindrome_dp_way(s);
    return longestPalindrome_dp_opt_way(s);
    return longestPalindrome_recursive_way2(s);
    return longestPalindrome_recursive_way(s);
}

int main(int argc, char**argv)
{
    string s = "abacdfgdcaba";
    if (argc > 1){
        s = argv[1];
    }
    cout <<  s << " : " << longestPalindrome(s) << endl;

    s = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123210012321001232100123210123";
    cout <<  s << " : " << longestPalindrome(s) << endl;
 
    //"illi"
    s = "iptmykvjanwiihepqhzupneckpzomgvzmyoybzfynybpfybngttozprjbupciuinpzryritfmyxyppxigitnemanreexcpwscvcwddnfjswgprabdggbgcillisyoskdodzlpbltefiz";
    cout <<  s << " : " << longestPalindrome(s) << endl;

    return 0;
}

#include <string>
using std::string;

class Solution {
    void longestPalindrome(const string& s, int b, int e, int &start, int &last) {
        int len = s.size();
        while (b >= 0 && e < len && s[b] == s[e])
            --b, ++e;
        ++b, --e;
        if (e - b > last - start) {
            start = b;
            last = e;
        }
    }

public:
    string longestPalindrome(string s) {
        int len = s.size();
        if (len == 0) return s;
        int start = 0, last = 0;
        for (int i=0; i<len-1; ++i) {
            longestPalindrome(s, i, i, start, last);
            longestPalindrome(s, i, i+1, start, last);
        }
        return s.substr(start, last-start+1);
    }
};

/// Source : https://leetcode.com/problems/longest-palindromic-substring/
/// Author : liuyubobobo
/// Time   : 2019-01-11

#include <iostream>

using namespace std;


/// Brute Force
/// Time Complexity: O(n^3)
/// Space Complexity: O(1)
class Solution {
public:
    string longestPalindrome(string s) {

        if(s == "") return s;

        int n = s.size();
        string res = s.substr(0, 1);
        for(int i = 0; i < n; i ++)
            for(int j = i + res.size(); j < n; j ++)
                if(ok(s, i, j) && j - i + 1 > res.size())
                    res = s.substr(i, j - i + 1);
        return res;
    }

private:
    bool ok(const string& s, int a, int b){
        for(; a < b && s[a] == s[b]; a ++, b --);
        return a >= b;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/longest-palindromic-substring/
/// Author : liuyubobobo
/// Time   : 2019-01-11

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Memory Search
/// State: is s[a...b] a palindrome?
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    string longestPalindrome(string s) {

        if(s == "") return s;

        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, -1)); // s[a...b]
        for(int len = n; len >= 1; len --)
            for(int start = 0; start + len - 1 < n; start ++)
                if(dfs(s, start, start + len - 1, dp))
                    return s.substr(start, len);
        return "";
    }

private:
    int dfs(const string& s, int a, int b,
             vector<vector<int>>& dp){

        if(a > b) return dp[a][b] = 0;
        if(a == b || (a + 1 == b && s[a] == s[b])) return dp[a][b] = 1;
        if(dp[a][b] != -1) return dp[a][b];

        if(s[a] != s[b]) return dp[a][b] = 0;
//        assert(s[a] == s[b]);
        return dp[a][b] = dfs(s, a + 1, b - 1, dp);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/longest-palindromic-substring/
/// Author : liuyubobobo
/// Time   : 2019-01-11

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Memory Search
/// State: is s.substr(start, len) a palindrome?
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    string longestPalindrome(string s) {

        if(s == "") return s;

        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n + 1, -1)); // start, len
        for(int len = n; len >= 1; len --)
            for(int start = 0; start + len - 1 < n; start ++)
                if(dfs(s, start, len, dp))
                    return s.substr(start, len);
        return "";
    }

private:
    int dfs(const string& s, int start, int len, vector<vector<int>>& dp){

        if(len <= 1) return dp[start][len] = 1;
        if(dp[start][len] >= 0) return dp[start][len];
        return dp[start][len] =
                (s[start] == s[start + len - 1] && dfs(s, start + 1, len - 2, dp));
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/longest-palindromic-substring/
/// Author : liuyubobobo
/// Time   : 2019-01-11

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Dynamic Programming
/// State: is s.substr(start, len) a palindrome?
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    string longestPalindrome(string s) {

        if(s == "") return s;

        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n + 1, true)); // start, len
        for(int len = 2; len <= n; len ++)
            for(int start = 0; start + len - 1 < n; start ++)
                dp[start][len] = (s[start] == s[start + len - 1] && dp[start + 1][len - 2]);
        for(int len = n; len >= 1; len --)
            for(int start = 0; start + len - 1 < n; start ++)
                if(dp[start][len])
                    return s.substr(start, len);
        return "";
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/longest-palindromic-substring/
/// Author : liuyubobobo
/// Time   : 2019-01-11

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Expand from center
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    string longestPalindrome(string s) {

        if(s == "") return s;

        int best = 0, n = s.size();
        string res = "";
        for(int center = 0; center < n; center ++){
            int len = 1, x;
            for(x = 1; x <= min(center, n - (center + 1)) && s[center - x] == s[center + x]; x ++)
                len += 2;
            if(len > best)
                best = len, res = s.substr(center - x + 1, len);
        }

        for(int center = 0; center + 1 < n; center ++)
            if(s[center] == s[center + 1]){
                int len = 2, x;
                for(x = 1; x <= min(center, n - (center + 2)) && s[center - x] == s[center + 1 + x]; x ++)
                    len += 2;
                if(len > best)
                    best = len, res = s.substr(center - x + 1, len);
            }
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/longest-palindromic-substring/
/// Author : liuyubobobo
/// Time   : 2019-07-25

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// LCS
/// Attention: Just get LCS between s and reverse(s) doesn't work
/// Some small fixes is needed
/// See here for details: https://leetcode.com/problems/longest-palindromic-substring/solution/
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    string longestPalindrome(string s) {

        if(s == "") return s;

        string rs = s;
        reverse(rs.begin(), rs.end());

        // lcs
        int n = s.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        string res = "";
        for(int i = 0; i < s.size(); i ++)
            for(int j = 0; j < rs.size(); j ++) {
                dp[i + 1][j + 1] = (s[i] == rs[j]) ? dp[i][j] + 1 : 0;
                if(dp[i + 1][j + 1] > res.size() && i - dp[i + 1][j + 1] + 1 == n - 1 - j)
                    res = s.substr(i - dp[i + 1][j + 1] + 1, dp[i + 1][j + 1]);
            }
        return res;
    }
};


int main() {

    cout << Solution().longestPalindrome("babad") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-palindromic-substring/
/// Author : liuyubobobo
/// Time   : 2019-07-25

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// LCS
/// Attention: Just get LCS between s and reverse(s) doesn't work
/// Some small fixes is needed
/// See here for details: https://leetcode.com/problems/longest-palindromic-substring/solution/
///
/// Using only O(n) space
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    string longestPalindrome(string s) {

        if(s == "") return s;

        string rs = s;
        reverse(rs.begin(), rs.end());

        // lcs
        int n = s.size();
        vector<vector<int>> dp(2, vector<int>(n + 1, 0));
        string res = "";
        for(int i = 0; i < s.size(); i ++)
            for(int j = 0; j < rs.size(); j ++) {
                dp[(i + 1) % 2][j + 1] = (s[i] == rs[j]) ? dp[i % 2][j] + 1 : 0;
                if(dp[(i + 1) % 2][j + 1] > res.size() && i - dp[(i + 1) % 2][j + 1] + 1 == n - 1 - j)
                    res = s.substr(i - dp[(i + 1) % 2][j + 1] + 1, dp[(i + 1) % 2][j + 1]);
            }
        return res;
    }
};


int main() {

    cout << Solution().longestPalindrome("babad") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-palindromic-substring/
/// Author : liuyubobobo
/// Time   : 2019-07-25

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Manacher's Algorithm
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    string longestPalindrome(string input) {

        string s = "#";
        for(char c: input)
            s += c, s += '#';

        int id = 0, maxright = 0;
        int rescenter = 0, reslen = 0;
        vector<int> r(s.size(), 0);
        for(int i = 1; i < s.size() - 1; i ++){
            r[i] = maxright > i ? min(r[2 * id - i], maxright - i) : 1;
            while(i - r[i] >= 0 && i + r[i] < s.size() && s[i + r[i]] == s[i - r[i]]) r[i] ++;
            r[i] --;

            if(i + r[i] > maxright) maxright = i + r[i], id = i;

            if(r[i] > reslen) reslen = r[i], rescenter = i;
        }

        return input.substr((rescenter - reslen) / 2, reslen);
    }
};


int main() {

    cout << Solution().longestPalindrome("babad") << endl;

    return 0;
}