Encontre o número de substrings válidas

Dada uma sequência de comprimento n, quero calcular quantas subsequências são possíveis com as seguintes características:

a) o comprimento da substring é par b) existe um caractere nesta substring cuja frequência é igual à metade do comprimento da substring.

Exemplo s="idafddfii", saída = 13

Explicação:

As substrings válidas são: "id", "da", "af", "fd", "df", "fi", "dafd", "afdd", "fddf", "ddfi", "dfii", "idafdd", "dafddf"

restrições:

1 <= n <= 10 potência 5

s consiste apenas em alfabetos ingleses minúsculos

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
    }

}

Meu código é executado em complexidade de tempo de O(n^2), quero reduzir essa complexidade de tempo. Qual é a abordagem correta para resolver isso em menos tempo?

Com base na resposta fornecida por @Unmitigated, tentei construir a frequência cumulativa de cada caractere assim, mas agora fiquei preso em como resolver o problema usando essa frequência cumulativa.

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