如何高效实现Java计算字符串中奇数长度子串的总数？

问题描述 #

需要编写Java函数计算给定字符串中奇数长度子串的总数，示例如下：

• 字符串"abcde"输出为9，对应子串：[a, abc, abcde, b, bcd, c, cde, d, e]
• 字符串"aaa"输出为4，对应子串：[a, aaa, a, a]

现有双重循环解法效率较低，希望得到高效实现思路。

现有低效解法 #

public static int countOddLengthSubstrings(String s) {
        int count = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if ((j - i + 1) % 2 != 0) { // 检查子串长度是否为奇数
                    count++;
                }
            }
        }
        return count;
    }

该解法时间复杂度为O(n²)，字符串长度较大时性能会显著下降。

高效实现思路：数学公式推导 #

无需遍历所有子串，通过数学规律可直接计算结果：

对于长度为n的字符串，统计所有奇数长度子串的总数，可简化为统一公式：
((n + 1) // 2) * ((n + 2) // 2)

推导逻辑：

1. 对每个可能的奇数长度l（1、3、5……≤n），长度为l的子串数量为n - l + 1
2. 将所有奇数l对应的数量求和，最终可化简为上述统一公式

验证示例：

• n=5（奇数）：((5+1)/2)*((5+2)/2)=3*3=9，与示例结果一致
• n=3（奇数）：((3+1)/2)*((3+2)/2)=2*2=4，与示例结果一致
• n=4（偶数）：((4+1)/2)*((4+2)/2)=2*3=6，实际子串为4个长度1的+2个长度3的，总数6，符合计算结果

高效Java实现 #

基于公式可写出时间复杂度为**O(1)**的代码：

public static int countOddLengthSubstrings(String s) {
    int n = s.length();
    return ((n + 1) / 2) * ((n + 2) / 2);
}

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