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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| 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); } };
|