Leetcode 1147: Longest Chunked Palindrome Decomposition

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/description/

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that: Each a_i is a non-empty string; Their concatenation a_1 + a_2 + ... + a_k is equal to text; For all 1 <= i <= k, a_i = a_{k+1 - i}.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7 Explanation:
We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Notes: The first response to this question is that we need to run a recursion with dp or memo, to gradually converge to the base case. See the code below,

class Solution {
public:
    int longestDecomposition(string text) {
        int res = 1, len = text.size();
        vector<vector<int>> memo(len, vector<int>(len, -1));
        dsf(text, 0, len-1, memo);
        return memo[0][len-1];
    }

private:
    int dsf(string &ts, int x, int y, vector<vector<int>> &memo) {
        if(x<0 || y>=ts.size() || x>y) return 0;
        if(memo[x][y] != -1) return memo[x][y];
        int t = 1;
        for(int i=x; i<=(y-x+1)/2; ++i) {
            if(ts.substr(x, i) == ts.substr(y-i+1, i)) {
                t = max(t, 2 + dsf(ts, x+i, y-i, memo));
            }
        }
        memo[x][y] = t;
        return memo[x][y];
    }
};

Then later on it is found that this question can be solved directly with greedy...

See the code below,

class Solution {
public:
    int longestDecomposition(string text) {
        int len = text.size();
        for(int i=1; i<=len/2; ++i) {
            if(text.substr(0, i) == text.substr(len-i, i))
                return 2 + longestDecomposition(text.substr(i, len-2*i));
        }
        return len == 0 ? 0 : 1;
    }
};