1147

1147. Longest Chunked Palindrome Decomposition (Hard)

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.

 

Example 1:

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

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

 

Constraints:

• 1 <= text.length <= 1000
• text consists only of lowercase English characters.

Companies:
Google

Related Topics:
Two Pointers, String, Dynamic Programming, Greedy, Rolling Hash, Hash Function

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int longestDecomposition(string s) {
        int i = 0, N = s.size(), ans = 0; 
        while (i < N / 2) {
            int len = 1;
            for (; i + len <= N / 2; ++len) {
                int j = 0;
                for (; j < len && s[i + j] == s[N - i - len + j]; ++j);
                if (j == len) break; // found match
            }
            if (i + len > N / 2) break; // match not found.
            ans += 2;
            i += len;
        } 
        return ans + (i < (N + 1) / 2);
    }
};