1147. Longest Chunked Palindrome Decomposition

You are given a string text. You should split it to k substrings (subtext1, subtext2, …, subtextk) such that:

• subtexti is a non-empty string.
• The concatenation of all the substrings is equal to text (i.e., subtext1 + subtext2 + … + subtextk == text).
• subtexti == subtextk - i + 1 for all valid values of i (i.e., 1 <= i <= k).

Return the largest possible value of k.

class Solution {
    int dp[1001][1001];
    bool equal(string& str, int leftl, int leftr, int rightl, int rightr) {
        if(leftl == rightl and leftr == rightr) return false;
        for(int i = leftl, j = rightl; i <= leftr; i++, j++) {
            if(str[i] != str[j]) return eqCache[key] = false;
        }
        return eqCache[key] = true;
    }
    int solution(string& str, int l, int r) {
        if(l >= r) return l == r ? 1 : 0;
        if(dp[l][r] != -1) return dp[l][r];
        dp[l][r] = 1;
        for(int i = 0; i <= (r-l+1)/2; i++) {
            if(equal(str,l,l+i,r-i,r)) {
                dp[l][r] = max(dp[l][r], solution(str,l+i+1, r-i-1) + 2);
            }
        }
        return dp[l][r];
    }

public:
    int longestDecomposition(string text) {
        memset(dp, -1, sizeof(dp));
        return solution(text, 0, text.size()-1);
    }
};