LeetCode 1147 - Longest Chunked Palindrome Decomposition

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/

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

https://www.codetd.com/en/article/6958381

Problem-solving ideas: This title is not too difficult, my approach is a greedy algorithm + dual pointers. First introducing two variables head and tail, respectively, equal to text [0] and text [-1]. If the head is equal to tail, which represents both the part may be composed of two palindromic segment, then make head equal text [1], tail equal text [-2]; if the two are not equal, so that head = head + text [0] , tail = text [-2] + tail, head until it equals the tail. Principle is equal to the tail head encounters each case, which represents a part of two palindromic segment, head and tail of the reset value.

code show as below:

class Solution(object):
    def longestDecomposition(self, text):
        """
        :type text: str
        :rtype: int
        """
        res = 0
        head_inx = 0
        tail_inx = len(text) - 1
        head = ''
        tail = ''
        while head_inx <= tail_inx and head_inx < len(text) and tail_inx >= 0:
            if head == '' and tail == '':
                head = text[head_inx]
                tail = text[tail_inx]
                head_inx += 1
                tail_inx -= 1
            elif head == tail:
                res += 2
                head = text[head_inx]
                tail = text[tail_inx]
                head_inx += 1
                tail_inx -= 1
            else:
                #head_inx += 1
                #tail_inx -= 1
                head = head + text[head_inx]
                tail = text[tail_inx] + tail
                head_inx += 1
                tail_inx -= 1
        res += 2 if  head == tail and head_inx - len(head) != tail_inx + len(tail) else 1
        return res if res != 0 else 1

https://zxi.mytechroad.com/blog/greedy/leetcode-1147-longest-chunked-palindrome-decomposition/
Solution: Greedy
Break the string when the shortest palindrome is found.
prefer to use string_view

Time complexity: O(n^2)
Space complexity: O(n)

  int longestDecomposition(string_view text) {    

    const int n = text.length();

    if (n == 0) return 0;

    for (int l = 1; l <= n / 2; ++l) {

      if (text.substr(0, l) == text.substr(n - l))

        return 2 + longestDecomposition(text.substr(l, n - 2 * l));

    }

    return 1;

  }

https://www.acwing.com/solution/LeetCode/content/3433/

(贪心) $O(n^2)$

1. 可以证明，如果能找到最短的字符串的前缀和后缀，则我们就将其拆分出来。这样迭代下去，一定是答案最大的。
2. 也就是说，不存在一个因为拆分出了长度更小的段，而导致整体答案变小的情况。
3. 所以我们可以通过枚举首尾的情况，来拆分字符串。
4. 对于当前字符串，从小到大枚举长度 len 表示期望的相同的段的长度，直到当前字符串长度的一半，然后枚举判断前缀和后缀子串是否相同。
5. 如果找到了一个相同的前后缀，则答案加 2，更新字符串重新迭代；否则答案加 1，退出迭代。

时间复杂度

• 最坏情况下，整个字符串不可拆分，此时需要 $O(n^2)$ 的时间去枚举验证。
• 故时间复杂度为 $O(n^2)$。

空间复杂度

• 没有用任何额外的数组，故空间复杂度为 $O(1)$。

    bool check(int l, int r, int len, const string& text) {
        for (int i = l, j = r - len + 1; j <= r; i++, j++)
            if (text[i] != text[j])
                return false;

        return true;
    }

    int longestDecomposition(string text) {
        int n = text.length();
        int l = 0, r = n - 1;
        int ans = 0;
        while (l <= r) {
            int length = r - l + 1;
            bool flag = false;
            for (int len = 1; len <= length / 2; len++)
                if (check(l, r, len, text)) {
                    l += len;
                    r -= len;
                    flag = true;
                    break;
                }

            if (!flag) {
                ans++;
                break;
            }
            else
                ans += 2;
        }
        return ans;
    }

https://xindubawukong.github.io/2019/08/15/Leetcode-1147-Longest-Chunked-Palindrome-Decomposition/

)的做法，枚举中间一块的长度，然后从中间向两边贪心，判断字符串相等使用hash。后来发现，直接从两边往中间贪心就行了。。连hash都不用，直接暴力判断。

    int longestDecomposition(string text) {
        int n = text.length();
        int ans = 0;
        int l = 0, r = 0;
        while (r * 2 + 1 < n) {
            if (text.substr(l, r - l + 1) == text.substr(n - r - 1, r - l + 1)) {
                ans += 2;
                l = r + 1;
                r = l;
                continue;
            }
            r++;
        }
        if (n % 2 == 0 && l == n / 2) return ans;
        return ans + 1;
    }

X. https://algorithm-notes-allinone.blogspot.com/2019/08/leetcode-1147-longest-chunked.html
The first response to this question is that we need to run a recursion with dp or memo, to gradually converge to the base case. See the code below,

class Solution {
public:
    int longestDecomposition(string text) {
        int res = 1, len = text.size();
        vector<vector<int>> memo(len, vector<int>(len, -1));
        dsf(text, 0, len-1, memo);
        return memo[0][len-1];
    }
 
private:
    int dsf(string &ts, int x, int y, vector<vector<int>> &memo) {
        if(x<0 || y>=ts.size() || x>y) return 0;
        if(memo[x][y] != -1) return memo[x][y];
        int t = 1;
        for(int i=x; i<=(y-x+1)/2; ++i) {
            if(ts.substr(x, i) == ts.substr(y-i+1, i)) {
                t = max(t, 2 + dsf(ts, x+i, y-i, memo));
            }
        }
        memo[x][y] = t;
        return memo[x][y];
    }