LeetCode 1147. 段式回文

约 7 分钟
文章信息 6 个分类 6 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节跳动
标签
字符串 动态规划 双指针 贪心 哈希函数 滚动哈希
目录

题目描述

✅ 1147. 段式回文

题意分析

把字符串 text 切成 $k$ 个非空子串 $a_1 a_2 \cdots a_k$，拼接起来正好等于原串，并且要求 $a_i = a_{k+1-i}$ 对所有 $i$ 成立——也就是这个切分序列本身是一个「回文」，只不过回文的单位从字符变成了子串。求 $k$ 的最大值。

要点一：相等指的是子串内容完全相同，不是互为反转。$a_1$ 必须逐字符等于 $a_k$，而不是 $a_k$ 的逆序。这与普通回文串的定义不同，读题时最容易搞反。

要点二：切分必须是连续且覆盖全串的，不能丢字符也不能重叠，所以第一段从头开始、最后一段到尾结束，两者长度必然相同。

要点三：$k$ 可以是奇数——中间允许剩下一段没有配对的 $a_{(k+1)/2}$，它不需要和任何段相等。

约束里 text 长度上限 1000，且只含小写字母。$n \le 1000$ 意味着 $O(n^2)$ 的做法（约 $10^6$ 次字符比较）完全可以接受，不必一上来就上滚动哈希或后缀自动机——这个规模是在告诉我们「朴素比较够用」。

边界：整串本身总是一个合法切分（$k = 1$），所以答案至少为 1，不存在无解；长度为 1 时答案就是 1；全同字符如 "aaaa" 时答案是 $n$，每个字符各成一段。

解法：双指针分段匹配

核心思路

每次只处理尚未切分的闭区间 [left, right]。若它还能产生一对外层段，那么两段必定是该区间等长且相等的前缀、后缀。因此从长度 1 开始比较，找到第一对相等片段后立即剥掉，再处理更小的中间区间。

为什么取“最短匹配”而不是继续找更长的？设最短相等前后缀为 $P$、长度为 $p$，某个最优分解的外层块为 $A$、长度为 $q$。必有 $p \le q$。若 $p<q$，则 $P$ 也是 $A$ 的前后缀；而最短真前后缀不会重叠，否则长度 $2p-q$ 的重叠部分会构成更短前后缀。因此 $A=P+M+P$（$M$ 可以为空）。把最优分解两端的每个 $A$ 都细分为 P | M | P（$M$ 为空时为 P | P），仍然关于中心对称，却得到更多段，与“最优”矛盾。故某个最优分解必取最短匹配；剥掉它后对中间区间归纳即可。

循环不变量是：[0, left) 与 (right, n-1] 已经被切成相互对称的最优外层段，answer 是这些段的数量；[left, right] 是唯一尚待处理的区间。

对剩余长度 remain，候选段长最多是 remain / 2，否则左右片段会重叠。若某个 len 匹配，就令 left += len、right -= len 并把答案加 2；若所有长度都不匹配，剩余区间不可能再产生外层配对，只能整体作为中间一段，答案加 1 后结束。

实现直接比较原串中的两个区间，不构造子串，也不在缓冲区头部插入字符。题目给出 $n \le 1000$，确定性的 $O(n^2)$ 字符比较足够快，同时避开滚动哈希的碰撞问题。

解题步骤

  • 初始化 left = 0、right = n - 1、answer = 0。
  • 当 left <= right 时，令 remain = right - left + 1，只枚举 1..remain/2 的片段长度，保证左右候选不重叠。
  • 用 equal(text, left, right-len+1, len) 逐字符比较当前前缀和后缀。第一次相等就是最短匹配，计入两段并收缩左右边界。
  • 若本轮没有任何匹配，或只剩一个字符，则整个剩余区间只能作为中心段：answer++ 后直接结束。
  • 返回 answer。每次匹配都会严格缩短区间，因此循环必然终止。

以 text = "ghiabcdefhelloadamhelloabcdefghi" 走一遍（答案是 7）：

依次找到最短匹配 "ghi"、"abcdef"、"hello"，每次计入 2 段；剩下 "adam" 没有相等且不重叠的前后缀，只计 1 段，得到

ghi | abcdef | hello | adam | hello | abcdef | ghi

答案为 7。边界用例 "aaa" 会先剥掉一对 "a"，再把中心 "a" 计为一段，答案为 3；"merchant" 找不到任何外层匹配，整串计一段。

代码实现

class Solution {
    public int longestDecomposition(String text) {
        int left = 0;
        int right = text.length() - 1;
        int answer = 0;

        while (left <= right) {
            boolean paired = false;
            int maxLen = (right - left + 1) / 2;
            for (int len = 1; len <= maxLen; len++) {
                if (equal(text, left, right - len + 1, len)) {
                    answer += 2;
                    left += len;
                    right -= len;
                    paired = true;
                    break;
                }
            }
            if (!paired) {
                return answer + 1;
            }
        }
        return answer;
    }

    private boolean equal(String text, int a, int b, int len) {
        for (int offset = 0; offset < len; offset++) {
            if (text.charAt(a + offset) != text.charAt(b + offset)) {
                return false;
            }
        }
        return true;
    }
}

func longestDecomposition(text string) int {
	left, right := 0, len(text)-1
	answer := 0

	for left <= right {
		paired := false
		maxLen := (right - left + 1) / 2
		for length := 1; length <= maxLen; length++ {
			if equalChunk(text, left, right-length+1, length) {
				answer += 2
				left += length
				right -= length
				paired = true
				break
			}
		}
		if !paired {
			return answer + 1
		}
	}
	return answer
}

func equalChunk(text string, a, b, length int) bool {
	for offset := 0; offset < length; offset++ {
		if text[a+offset] != text[b+offset] {
			return false
		}
	}
	return true
}

复杂度分析

  • 时间复杂度：$O(n^2)$。一次匹配到长度 $p$ 的工作量是 $1+2+\cdots+p=O(p^2)$；各轮剥掉的 $p$ 之和不超过 $n/2$，故平方和不超过 $O(n^2)$，最后一次无匹配扫描也至多 $O(n^2)$。
  • 空间复杂度：$O(1)$，只保存边界、长度和计数；没有创建候选子串。返回值之外也没有递归栈。

关键点总结

  • 段式回文比较的是两段原始内容，不是把右段反转后比较。
  • 状态只需 [left, right]：区间外已经最优配对，区间内尚未处理。每次成功必须同时收缩两端相同长度。
  • 枚举上界是剩余长度的一半，防止左右候选重叠；找不到匹配时，剩余内容只能整体成为唯一的中心段。
  • 最短匹配优先是贪心成立的关键；面试时要说明 border 的细化性质，而不是只说“短的段数更多”。
  • $n \le 1000$ 时直接比较最稳妥。若约束升到 $10^5$，可用双哈希把区间比较降为均摊 $O(1)$，但必须说明碰撞处理。

易错点总结

  • 把右段反转后比较：text = "volvo" 中合法切分是 "vo" | "l" | "vo"；右段必须仍是 "vo"，不能按字符回文去比较 "ov"。
  • 让候选长度超过剩余长度的一半：中心会被两段重复占用。text = "aaa" 的答案是 3，不可能计成 4。
  • 命中后继续寻找更长匹配：text = "aaaa" 若取 "aa" | "aa" 只得到 2 段；第一对长度 1 的匹配可得到 4 段。
  • 无匹配时继续移动单侧指针：text = "merchant" 的剩余区间本应整体算一段；移动一侧会破坏“前后缀等长”的约束。
  • 无匹配时返回当前计数：text = "abc" 会错误返回 0，必须为中心剩余段补 1。
  • 用 substring/切片构造每个候选：复杂度阶数不变，却制造大量临时对象；按下标逐字符比较即可。

相似题目

题目 难度 考察点
131. 分割回文串 中等 同为切分字符串，但每段自身要是回文，需回溯枚举所有方案
214. 最短回文串 困难 求最长回文前缀，KMP 的 next 数组或滚动哈希是标准工具
459. 重复的子字符串 简单 判断能否由某段重复拼成，同样是「前缀与后缀内容相等」的思路
28. 找出字符串中第一个匹配项的下标 简单 子串匹配的基础题，是把本题优化到 $O(n)$ 所需哈希/KMP 技术的起点
5. 最长回文子串 中等 字符级回文的中心扩展，与本题「段级回文」形成概念对照
516. 最长回文子序列 中等 允许丢弃字符的区间 DP，可与本题的贪心可行性作对比