vvrf / DSA.log

问题拆解

统计字符串中回文子串的个数，位置不同就算不同的子串，哪怕内容一样。朴素做法是枚举全部 O(n²) 个子串、逐一花 O(n) 判断回文，总共 O(n³)，对 n = 1000 的上限太吃力。

浪费在哪里？判断 "abcba" 时其实已经顺路看过 "bcb" 和 "c"——回文之间有嵌套结构：一个回文剥掉两端还是回文。反过来利用这一点：从中心出发向两侧扩展，只要两端字符相等就继续，每扩一步就发现一个新的回文。这样同一个中心的所有回文一趟扫出来，判断的功夫一点不浪费。

每个回文子串都有唯一的中心：长度为奇数时中心是一个字符，长度为偶数时中心是相邻两个字符的缝隙。所以中心一共 n + (n-1) = 2n - 1 个，逐个扩展就能不重不漏地数完所有回文。

最容易漏的就是偶数长度：只枚举 n 个单字符中心，"aa"、"abba" 这类回文会被整体漏掉。

中心扩展计数

把“从给定的左右端点向外扩”抽成一个辅助过程，奇数中心传 (i, i)，偶数中心传 (i, i+1)，两类中心统一处理。

public int countSubstrings(String s) {
    int n = s.length(), count = 0;
    for (int i = 0; i < n; i++) {
        count += expand(s, i, i);     // 奇数长度，中心是单字符
        count += expand(s, i, i + 1); // 偶数长度，中心是缝隙
    }
    return count;
}

private int expand(String s, int l, int r) {
    int count = 0;
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        count++; // 每扩一步就是一个新回文
        l--;
        r++;
    }
    return count;
}

def countSubstrings(s: str) -> int:
    def expand(l: int, r: int) -> int:
        count = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1  # 每扩一步就是一个新回文
            l -= 1
            r += 1
        return count

    return sum(expand(i, i) + expand(i, i + 1) for i in range(len(s)))

func countSubstrings(s string) int {
    expand := func(l, r int) int {
        count := 0
        for l >= 0 && r < len(s) && s[l] == s[r] {
            count++ // 每扩一步就是一个新回文
            l--
            r++
        }
        return count
    }
    total := 0
    for i := range s {
        total += expand(i, i)   // 奇数长度，中心是单字符
        total += expand(i, i+1) // 偶数长度，中心是缝隙
    }
    return total
}

pub fn count_substrings(s: String) -> i32 {
    let b = s.as_bytes();
    let n = b.len();
    let expand = |mut l: i32, mut r: i32| -> i32 {
        let mut count = 0;
        while l >= 0 && (r as usize) < n && b[l as usize] == b[r as usize] {
            count += 1; // 每扩一步就是一个新回文
            l -= 1;
            r += 1;
        }
        count
    };
    (0..n as i32).map(|i| expand(i, i) + expand(i, i + 1)).sum()
}

值得体会的是计数的位置：count 在循环内每次比较成功就加一，因为“扩一步成功”本身就意味着一个新的回文子串诞生——(i, i) 出发扩两次，说明 s[i]、s[i-1..i+1]、s[i-2..i+2] 三个回文各计一次。偶数中心第一次比较就是在检查 s[i] == s[i+1]，两字符不等则立刻返回 0，天然不会多算。

这个框架和第 5 题“最长回文子串”完全同源：那道题在扩展过程中记录最长的区间，这道题改成累加成功的步数。中心扩展是一套框架、两种统计。

复杂度

指标	复杂度	原因
时间	`O(n²)`	2n-1 个中心，每个最多向外扩 n/2 步
空间	`O(1)`	只用常数个指针和计数器

可以迁移的模式

回文问题优先想“中心扩展”，记住中心有 2n-1 个，偶数缝隙别漏；
把“从某状态向外探”的动作抽成辅助函数，奇偶两类中心就能共用一套代码；
同一个枚举框架换掉统计动作（计数、记最长、存区间），就是一族不同的题。

如果字符串长到 O(n²) 也扛不住，再去了解 Manacher 算法——它把中心扩展的重复功夫也省掉了，但面试场景下中心扩展几乎总是够用的。