原文链接: https://leetcode-cn.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)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

 

Constraints:

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

中文题目

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。

举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。

 

给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。

如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, ..., a_k：

• 每个 a_i 都是一个非空字符串；
• 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同；
• 对于所有1 <= i <= k，都有 a_i = a_{k+1 - i}。

 

示例 1：

输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2：

输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。

示例 3：

输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。

示例 4：

输入：text = "aaa"
输出：3
解释：我们可以把字符串拆分成 "(a)(a)(a)"。

 

提示：

• text 仅由小写英文字符组成。
• 1 <= text.length <= 1000

通过代码

高赞题解

解题思路

左右两个指针
1.左边先走找到和右边指针相等的
2.然后右边递减判断相等是否能够覆盖到左指针此次开始的位置
3.如果覆盖到左边此次开始的位置表示可以划分为相同的段
4.如果不能覆盖，左边继续往右走，回到步骤1
时间复杂度O(n)，空间复杂度O(1)
为啥题解里面这么多dp的。
看到好多题解的代码都是用substr判断相等的，测试样例里面如果来个 aaa..(非常多a)aabaaa..(相同多的a)aab那不就退化成O(n^2)了么
不过好像官方测试样例里面确实没有这样的样例。。

代码

class Solution {
    public int longestDecomposition(String text) {
        int i = 0, j = text.length() - 1;
        int ans = 0;
        int i0 = 0, j0 = text.length() - 1, k = 0;
        while (i < j) {
            while (i < j) {
                if (text.charAt(i++) == text.charAt(j)) {
                    break;
                }
            }
            k = i--;
            while (i >= i0) {
                if (text.charAt(j) != text.charAt(i)) {
                    break;
                }
                i--;
                j--;
            }
            if (i < i0) {
                ans += 2;
                i0 = k;
            } else {
                j = j0;
            }
            i = k;
            j0 = j;
        }
        ans = i0 > j0 ? ans : ans + 1;
        return ans;
    }
}

统计信息

通过次数	提交次数	AC比率
4314	7693	56.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言