Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1147.html

1147. Longest Chunked Palindrome Decomposition

Level

Hard

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)”.

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:

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

Solution

Use two pointers. Initially, low and high point to the minimum index and the maximum index of text respectively. Also maintain the previous pointers prevLow and prevHigh, which are initially equal to low and high respectively.

Each time starting from low, look for the first character that equals the character at high. If such a character is found, loop in reversing order to find the longest chunk that can be covered. If the left side can be covered, increase the number of chunks by 2 and continue searching in a shorter substring. Otherwise, continue move the low to the right to look for a character that equals the character at high. Finally, if prevLow <= prevHigh, then a new chunk is added at the middle. Finally, return the number of chunks.

  • class Solution {
    public int longestDecomposition(String text) {
        int chunks = 0;
        int low = 0, high = text.length() - 1;
        int prevLow = low, prevHigh = high;
        int nextLow = 0;
        while (low < high) {
            while (low < high && text.charAt(low) != text.charAt(high))
                low++;
            if (low == high)
                low--;
            nextLow = low + 1;
            while (low >= prevLow) {
                if (text.charAt(low) == text.charAt(high)) {
                    low--;
                    high--;
                } else
                    break;
            }
            if (low < prevLow) {
                chunks += 2;
                prevLow = nextLow;
            } else
                high = prevHigh;
            low = nextLow;
            prevHigh = high;
        }
        if (prevLow <= prevHigh)
            chunks++;
        return chunks;
    }
}

  • // OJ: https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
// 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);
    }
};

  • class Solution:
    def longestDecomposition(self, text: str) -> int:
        n = len(text)
        if n < 2:
            return n
        for i in range(n // 2 + 1):
            if text[:i] == text[-i:]:
                return 2 + self.longestDecomposition(text[i:-i])
        return 1

############

# 1147. Longest Chunked Palindrome Decomposition
# https://leetcode.com/problems/longest-chunked-palindrome-decomposition/

class Solution:
    def longestDecomposition(self, text: str) -> int:
        n = len(text)
        res, l, r = 0, "", ""
        
        for a,b in zip(text, text[::-1]):
            l, r = l + a, b + r
            
            if l == r:
                res, l, r = res + 1, "", ""
        
        return res

All Problems

All Solutions