面试题：统计压缩后为回文的奇偶长度子串数量

问题描述 #

给定字符串（示例：S="abbba"），对每个子串执行连续重复字符压缩（例如子串"bbba"压缩后为"ba"），统计压缩结果为回文的子串中，奇数长度和偶数长度的数量。

注：无压缩条件时，可通过二维DP直接统计回文子串，但压缩条件大幅提升了问题复杂度。

核心分析 #

压缩后的字符串本质是原串的"去连续重复"版本——相邻字符必然不同。因此，判断子串压缩后是否为回文，等价于判断该子串对应的特征序列子区间是否为回文：

• 先将原串转换为特征序列：把连续相同的字符分组，每组记录字符、起始索引、结束索引（例如"abbba"的特征序列为[('a',0,0), ('b',1,3), ('a',4,4)]）。
• 原串任意子串的压缩结果，对应特征序列中某段连续区间的字符拼接（若子串覆盖特征x到y的部分/全部字符，压缩后就是特征x到y的字符序列）。

解法步骤 #

1. 预处理生成特征序列 #

遍历原串，合并连续相同字符，得到：

• chars：特征序列的字符列表（如['a','b','a']）
• starts：每组字符的起始索引（如[0,1,4]）
• ends：每组字符的结束索引（如[0,3,4]）
• lengths：每组字符的长度（如[1,3,1]）

2. 统计特征序列中的回文区间对应的原串子串 #

遍历特征序列的所有回文区间（用中心扩展法高效枚举，时间复杂度O(n²)，n为特征序列长度），分两种情况计算对应原串子串的奇偶长度数量：

情况1：单特征区间（i == j）

对应原串中组i内的所有子串，压缩后为单个字符（必然是回文）。设组长度为k：

• 奇数长度子串数量：((k + 1) // 2) * ((k + 2) // 2)
• 偶数长度子串数量：(k // 2) * ((k + 1) // 2)

情况2：多特征区间（i < j）

仅当chars[i..j]是回文时，统计对应原串子串：

• 组i的起始选择数为k_i = ends[i] - starts[i] + 1，组j的结束选择数为k_j = ends[j] - starts[j] + 1
• 统计组i中奇数索引数量odd_i、偶数索引数量even_i；组j中奇数索引数量odd_j、偶数索引数量even_j
• 奇数长度子串数量：odd_i * odd_j + even_i * even_j（子串长度奇偶性由起始、结束索引的奇偶性是否相同决定）
• 偶数长度子串数量：odd_i * even_j + even_i * odd_j

3. 累加所有回文区间的统计结果 #

将所有符合条件的子串奇偶长度数量分别累加，得到最终结果。

示例验证（S="abbba"） #

特征序列参数：

• 组0：k=1，odd_i=0，even_i=1
• 组1：k=3，odd_i=2，even_i=1
• 组2：k=1，odd_i=0，even_i=1

统计过程：

1. 单特征区间：
   • 组0：奇数+1，偶数+0
   • 组1：奇数+4，偶数+2
   • 组2：奇数+1，偶数+0
2. 多特征回文区间（i=0,j=2，字符序列"aba"是回文）：
   • 奇数+1，偶数+0

最终结果：奇数长度子串7个，偶数长度子串2个

内容的提问来源于stack exchange，提问作者Maggi Iggam