Algorithm

Problem Name: 1147. Longest Chunked Palindrome Decomposition

Problem Link: https://leetcode.com/problems/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.

 

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.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


const longestDecomposition = function(text) {
  let res = 0,
    n = text.length
  let l = '',
    r = ''
  for (let i = 0; i  <  n; ++i) {
    l = l + text.charAt(i)
    r = text.charAt(n - i - 1) + r
    if (l === r) {
      ++res
      l = ''
      r = ''
    }
  }
  return res
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
text = "ghiabcdefhelloadamhelloabcdefghi"

Output

x
–
+
cmd
7

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def longestDecomposition(self, S: str) -> int:
        res, l, r = 0, "", ""
        for i, j in zip(S, S[::-1]):
            l, r = l + i, j + r
            if l == r:
                res, l, r = res + 1, "", ""
        return res
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
text = "ghiabcdefhelloadamhelloabcdefghi"

Output

x
–
+
cmd
7
Advertisements

Demonstration

Previous
#1146 Leetcode Snapshot Array Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1148 Leetcode Article Views I Solution in SQL Leetcode