Longest Chunked Palindrome Decomposition Solutions in C++

/// Source : https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
/// Author : liuyubobobo
/// Time   : 2019-08-03

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n^3)
/// Space Complexity: O(n^2)
class Solution {

private:
    string s;

public:
    int longestDecomposition(string text) {

        int n = text.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        s = text;
        return go(0, n - 1, dp);
    }

private:
    int go(int l, int r, vector<vector<int>>& dp){
        if(l > r) return 0;
        if(l == r) return 1;
        if(dp[l][r] != -1) return dp[l][r];

        int len = r - l + 1;
        len /= 2;
        int res = 1;
        for(int ll = 1; ll <= len; ll ++)
            if(s.substr(l, ll) == s.substr(r - ll + 1, ll))
                res = max(res, 2 + go(l + ll, r - ll, dp));
        return dp[l][r] = res;
    }
};


int main() {

    cout << Solution().longestDecomposition("ghiabcdefhelloadamhelloabcdefghi") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
/// Author : liuyubobobo
/// Time   : 2019-08-04

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Space Optimized
///
/// Time Complexity: O(n^3)
/// Space Complexity: O(n)
class Solution {

private:
    string s;
    int n;

public:
    int longestDecomposition(string text) {

        n = text.size();
        vector<int> dp(n, -1);
        s = text;
        return go(0, dp);
    }

private:
    int go(int l, vector<int>& dp){
        if(n % 2){
            if(l == n / 2) return 1;
            if(l > n /2 ) return 0;
        }
        else if(l >= n / 2) return 0;

        if(dp[l] != -1) return dp[l];

        int res = 1;
        for(int len = 1; l + len <= n / 2; len ++)
            if(s.substr(l, len) == s.substr(n - l - len, len))
                res = max(res, 2 + go(l + len, dp));
        return dp[l] = res;
    }
};


int main() {

    cout << Solution().longestDecomposition("ghiabcdefhelloadamhelloabcdefghi") << endl;
    cout << Solution().longestDecomposition("aaa") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
/// Author : liuyubobobo
/// Time   : 2019-08-04

#include <iostream>
#include <vector>

using namespace std;


/// Greedy
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    string s;
    int n;

public:
    int longestDecomposition(string text) {

        n = text.size();
        s = text;
        return go(0);
    }

private:
    int go(int l){

        if(n % 2){
            if(l == n / 2) return 1;
            if(l > n /2 ) return 0;
        }
        else if(l >= n / 2) return 0;

        for(int len = 1; l + len <= n / 2; len ++)
            if(s.substr(l, len) == s.substr(n - l - len, len))
               return 2 + go(l + len);
        return 1;
    }
};


int main() {

    cout << Solution().longestDecomposition("ghiabcdefhelloadamhelloabcdefghi") << endl;
    cout << Solution().longestDecomposition("aaa") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
/// Author : liuyubobobo
/// Time   : 2019-08-04

#include <iostream>
#include <vector>

using namespace std;


/// Greedy - Iterative Implementation
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

public:
    int longestDecomposition(string text) {

        int n = text.size();
        int l = 0, r = n - 1, res = 0;
        string ls = "", rs = "";
        while(l < r){
            ls += text[l ++], rs = string(1, text[r --]) + rs;
            if(ls == rs) res += 2, ls = rs = "";
        }
        return res + (l == r || ls != "");
    }
};


int main() {

    cout << Solution().longestDecomposition("ghiabcdefhelloadamhelloabcdefghi") << endl;
    cout << Solution().longestDecomposition("aaa") << endl;

    return 0;
}