# chunked-palindrome

## Chunked Palindrome

### 题目描述

```
Normal palindrome is defined as a string that reads the same backwards as forwards, for example "abccba".
Chunked palindrome is defined as a string that you can split into chunks and it will form a palindrome.
For example, "volvo". You can split it into (vo)(l)(vo). Let A = "vo", B = "l", so the original string is ABA which is a palindrome.

Given a string str, find the maximum number of chunks we can split that string to get a chuncked palindrome.

Example 1:

Input: "valve"
Output: 1
Explanation: You can't split it into multiple chunks so just return 1 (valve)
Example 2:

Input: "voabcvo"
Output: 3
Explanation: (vo)(abc)(vo)
Example 3:

Input: "vovo"
Output: 2
Explanation: (vo)(vo)
Example 4:

Input: "volvolvo"
Output: 5
Explanation: (vo)(l)(vo)(l)(vo)
Example 5:

Input: "volvol"
Output: 2
Explanation: (vol)(vol)
Example 6:

Input: "aaaaaa"
Output: 6
Explanation: We can split it into (aaa)(aaa), but the optimal split should be (a)(a)(a)(a)(a)(a)
Questions from the same interview:

Product of K consecutive numbers
```

## 思路

给定一个字符串，让求出最多可以切成分块的回文，每一个切分可以是一个子字符串，或者单个字符。

例如， `"aaaaaa"`， 可以切分成 `"aaa)(aaa)" - 2`， 但是这里要求最多分块， 这样就是最多的`"(a)(a)(a)(a)(a)(a)" - 6`

#### 解法一，

分析， 满足回文字符串的要求是，从前读和从后读是一样的， 例如， `"aba"， "anna"，"madam"` 等

那么这里就可以分别从前`（l）`和从后`（r）`扫描，`l` 和 `r` 记录前后扫描的`index`， 然后用`pre_l` and `pre_r` 记录前一次扫描到的可以分块的回文位置，

如果子字符串相同（substr（pre\_l, l + 1) 这里包含边界），结果 +2，继续扫描。

如果最后剩余一个（奇数个chunk）， 那么直接结果 +1， 否则偶数个chunk， 直接返回结果

例如：`"volvolvo"`

![alt text](/files/-LmDYFiDdcQT0zlbJi11)

#### 复杂度分析

**时间复杂度：`O(N^2) - N is the s length, s.substring()时间复杂度是O(n)`**

**空间复杂度：`O(1) - 没有额外的空间`**

#### 解法二

从解法一中我们可以看到`palindome` 左右对称， 所以可以从左和右，用递归求解。

如下图例子， 可以从左起子字符串匹配最右起的子字符串。绿色框框，如果匹配， 递归的计算最长的回文，即每次碰到回文就计算 +2， 直到最后字符串中没有匹配的回文，或者是匹配到最后， 退出， 返回结果。

例如：`"volvolvo"`

![alt text](/files/-LmDYFiFmPV7sCDMDJL3)

## 代码 （Java）

**解法一**

```java
class ChunkedPalindrom {
    public static int maxChunkedPalindrome2(String s) {
        if (s == null || s.length() == 0) return 0;
        int l = 0;
        int r = s.length() - 1;
        int max = 0;
        int preL = l;
        int preR = r;
        while (l < r) {
          String prefix = s.substring(preL, l + 1); // include right
          String sufix = s.substring(r, preR + 1);
          if (prefix.equals(sufix)) {
            preL = l + 1;
            preR = r - 1;
            max += 2;
          }
          l++;
          r--;
        }
        if (preL <= preR) max++;
        System.out.println("max chunk palindrom: " + max);
        return max;
      }
  }
```

**解法二**

```java
class ChunkedPalindrome {
    public static int maxChunkedPalindrome(String s) {
        if (s == null || s.length() == 0) return 0;
        return helper(s, 0, 0, s);
      }

      private static int helper(String curr, int count, int len, String s) {
        // no substring left, return current count
        if (curr == null || curr.isEmpty()) return count;
        if (curr.length() <= 1) {
          if (count != 0 && s.length() - len <= 1) {
            return count + 1;
          } else return 1;
        }
        int currLen = curr.length();
        // get left and right substring and compare
        for (int i = 0; i < currLen / 2; i++) {
          String left = curr.substring(0, i + 1);
          String right = curr.substring(currLen - 1 - i, currLen);
          if (left.equals(right)) {
            // if left and right match, then continue match the rest substring (s - left - right)
            return helper(curr.substring(i + 1, currLen - 1 - i),
                count + 2, len + (i + 1) * 2, s);
          }
        }
        return count + 1;
      }
  }
```

## 参考（References）

1. [Longest Possible Chunked Palindrome](https://www.geeksforgeeks.org/longest-possible-chunked-palindrome/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://snowan.gitbook.io/study-notes/google/chunked-palindrome-cn.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.