1147. Longest Chunked Palindrome Decomposition

Description

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)(tep)(za)(pre)(a)(nt)(a)".

 

Constraints:

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

 

Solutions

Solution: Two Pointers

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} text
 * @return {number}
 */
const longestDecomposition = function (text) {
  const n = text.length;
  let left = 0;
  let right = n - 1;
  let leftSub = '';
  let rightSub = '';
  let result = 0;

  while (left < right) {
    leftSub += text[left];
    rightSub = `${text[right]}${rightSub}`;

    if (leftSub === rightSub) {
      result += 2;
      leftSub = '';
      rightSub = '';
    }
    left += 1;
    right -= 1;
  }
  const remain = n % 2 || leftSub ? 1 : 0;

  return result + remain;
};