如何优化满足特定条件的有效子串计数算法的时间复杂度？

给定长度为n的小写英文字符串，需统计满足以下两个条件的子串数量：

• 子串长度为偶数；
• 子串中存在某个字符的出现次数等于子串长度的一半。

示例
输入字符串s="idafddfii"，输出结果为13。
解释
符合条件的子串为："id", "da", "af", "fd", "df", "fi", "dafd", "afdd", "fddf", "ddfi", "dfii", "idafdd", "dafddf"

约束条件

• 1 ≤ n ≤ 10^5；
• 字符串仅由小写英文字母组成。

当前Java实现的时间复杂度为O(n²)，无法高效处理大数据量，需优化至更低时间复杂度：

public class Main {

    public static long solve(String s) {
        int n = s.length();
        long result = 0;
    
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                int len = j - i + 1;
                // Only check even-length substrings
                if (len % 2 == 0) {
                    if (isValid(freq, len)) {
                        result++;
                    }
                }
            }
        }
        return result;
    }
    
    private static boolean isValid(int[] freq, int len) {
        int half = len / 2;
        for (int count : freq) {
            if (count == half) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        String s1 = "aaaaid";
        String s2 = "aidfg";
        String s3 = "ababbab";
    
        System.out.println(solve(s1)); // Output: 3
        System.out.println(solve(s2)); // Output: 4
        System.out.println(solve(s3)); // Output: 8
    }

}

已参考建议尝试构建字符的累积频率数组，但不知后续如何利用该数组完成求解，代码如下：

import java.util.*;
public class Main {

    public static int solve(String s) {
        int n = s.length();
        int result = 0;
        Map<Character, int[]> map = new HashMap<>();
        for(int i=0; i<n; i++) {
            char ch = s.charAt(i);
            int[] cnt = map.getOrDefault(ch, new int[n]);
            cnt[i] += i == 0 ? 1 : cnt[i-1]+1;
            map.put(ch, cnt);
        }
        for(char c : map.keySet()) {
            System.out.println(c + ":" + Arrays.toString(map.get(c)));
        } 
        // what to do next
        return result;
    }

    public static void main(String[] args) {
        String s = "idafddfii";
        int output = solve(s);
        System.out.println(output); // Output: 13
    }
}

恳请提供将算法优化至更低时间复杂度的正确方法，以及如何利用累积频率数组完成求解。

核心思路 #

我们可以把问题转化为：对每个字符c，统计所有偶数长度子串中c的出现次数恰好等于子串长度一半的数量，最后去重（避免子串因多个字符满足条件被重复计数）。关键是利用前缀频率推导的等式+哈希表来快速统计：

对于子串s[i+1..j]（长度为j-i，偶数），设prefix[k][c]为前k个字符中c的出现次数，条件可转化为：
prefix[j][c] - prefix[i][c] = (j-i)/2
整理后得到：
2*prefix[j][c] - j = 2*prefix[i][c] - i

这意味着，对每个位置j，只需统计之前有多少个位置i满足上述等式，就能得到以j结尾、符合条件的子串数量（针对字符c）。

具体实现步骤 #

1. 针对单个字符统计：
   对每个字符c，用哈希表记录2*prefix[i][c]-i的出现次数，遍历字符串时计算当前位置的对应值，累加哈希表中已有该值的次数，再更新哈希表。
2. 去重处理：
   部分子串会同时满足多个字符的条件（比如"abba"中a和b的出现次数均为2），这类子串会被重复统计，需要单独计算重复数量并从总数中减去。

优化后的Java代码 #

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static long solve(String s) {
        int n = s.length();
        long total = 0;

        // 统计每个字符对应的符合条件的子串数
        for (char target = 'a'; target <= 'z'; target++) {
            Map<Long, Integer> countMap = new HashMap<>();
            countMap.put(0L, 1);
            long currentPrefix = 0;
            for (int j = 1; j <= n; j++) {
                if (s.charAt(j - 1) == target) {
                    currentPrefix++;
                }
                long key = 2 * currentPrefix - j;
                total += countMap.getOrDefault(key, 0);
                countMap.put(key, countMap.getOrDefault(key, 0) + 1);
            }
        }

        // 减去重复统计的子串：由两个字符组成且各占一半次数的子串
        long duplicate = 0;
        for (char c1 = 'a'; c1 <= 'z'; c1++) {
            for (char c2 = c1 + 1; c2 <= 'z'; c2++) {
                Map<Long, Integer> map = new HashMap<>();
                map.put(0L, 1);
                long currentDiff = 0;
                for (int j = 1; j <= n; j++) {
                    char ch = s.charAt(j - 1);
                    if (ch == c1) {
                        currentDiff++;
                    } else if (ch == c2) {
                        currentDiff--;
                    }
                    duplicate += map.getOrDefault(currentDiff, 0);
                    map.put(currentDiff, map.getOrDefault(currentDiff, 0) + 1);
                }
            }
        }

        return total - duplicate;
    }

    public static void main(String[] args) {
        String s1 = "aaaaid";
        String s2 = "aidfg";
        String s3 = "ababbab";
        String s4 = "idafddfii";

        System.out.println(solve(s1)); // Output: 3
        System.out.println(solve(s2)); // Output: 4
        System.out.println(solve(s3)); // Output: 8
        System.out.println(solve(s4)); // Output: 13
    }
}

复杂度分析 #

• 时间复杂度：O(26n + 26²n) = O(n)，26为常数，完全适配n≤1e5的场景；
• 空间复杂度：O(n)，每个哈希表最多存储n个键值对。

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