查找有效子字符串的数量

给定一个长度为 n 的字符串，我想计算有多少个子字符串可能具有以下特征：

a) 子串长度为偶数 b) 该子串中存在一个字符，其频率等于子串长度的一半。

例如 s="idafddfii", 输出 = 13

解释：

有效的子字符串为：“id”、“da”、“af”、“fd”、“df”、“fi”、“dafd”、“afdd”、“fddf”、“ddfi”、“dfii”、“idafdd”、“dafddf”

限制：

1 <= n <= 10 的 5 次方

s 仅由小写英文字母组成

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
    }

}

我的代码运行时间复杂度为 O(n^2)，我想降低这个时间复杂度，在更短的时间内解决这个问题的正确方法是什么。

根据@Unmitigated 提供的答案，我尝试像这样构建每个字符的累积频率，但现在不知道如何使用这个累积频率来解决问题。

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
    }
}