查找奇数长度子串的总数

Question

我正在尝试编写一个函数来计算给定字符串中奇数长度子字符串的总数。例如，对于字符串“abcde”，仅考虑奇数长度的子字符串（[a, abc, abcde, b, bcd, c, cde, d, e]），输出应为 9。同样，对于字符串“aaa”，输出应为 4 ([a, aaa, a, a])。我很感激任何关于如何在 java 中有效实现这一点的见解。

我无法想出有效的解决方案。

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) { // Checking if length is odd
                    count++;
                }
            }
        }
        return count;
    }

Answer 1

如果你只关心奇数长度子串的数量，不进行重复数据删除，那么问题可以在 O(1) 时间内解决。

考虑字符串"abcde"。在我们的例子中，我们只关注以第一个字符开头的子字符串"a"。有 3 个奇数长度子串："a"、"abc"、 和"abcde"。

现在让我们重点关注从第二个字符开始的子字符串"b"。一个类似的问题是字符串中有多少个以第一个字符开头的奇数长度子串"bcde"？我们看到有"b"和"bcd"。对于第三个字符，我们有"c"和"cde"，对于第四个和第五个字符，我们分别有"d"和。"e"

我相信我们已经可以在这里看到一些模式。对于长度为 的字符串n，从第一个字符开始的奇数长度子串的数量为ceil(n/2)。所以序列是，从（本质上是A0045260, 1, 1, 2, 2, 3, 3, 4, 4, ... ）开始。找到奇数长度子串的总数就是该序列的部分和，根据 OEIS（整数序列在线百科全书），该数将为。n=0floor((n+1)^2 / 4)

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