Number of substrings possible with even characters
Assuming that your alphabet has constant size, you can solve your problem in linear time in the length of the input string.
Let  $\Sigma = \{a_1, a_2, \dots, a_m\}$ be your alphabet and $s = s_1 s_2 \dots s_n$ be your input string.
For $i=0, \dots, n$, and $j=1,\dots,m$ let $n_j(i)$ be $0$ iff the number of occurrences of $a_j$ in $s_1 \dots s_i$ is even and $1$ otherwise.
Let $\eta(i) \in \{0,1\}^{m}$ be the vector $(\eta_1(i), \dots, \eta_m(i))$.
Consider any substring $s_{hk} = s_{h+1},s_{h+2}, \dots, s_k$ of $s$, where $0 \le h &lt; k \le n$.
The number of occurrences of each $a_j$ in $s_{hk}$ is even if and only if $\eta(k)-\eta(h) = (0, \dots, 0)$, where the difference is taken modulo $2$, i.e., iff $\eta(k)=\eta(h)$.
Then your problem is equivalent to counting the number of unordered pairs of distinct indices $\{h,k\}$ for which $\eta(h)=\eta(k)$.
This can be done as follows: given $x \in \{0,1\}^{m}$ let $\alpha(x)$ be the number of times of $x$ appears in $\eta(0), \dots, \eta(n)$, so that the number of unordered pairs $\{h,k\}$ for which $\eta(h) = \eta(k) = x$ is $\binom{\alpha(x)}{2} = \frac{\alpha(x) (\alpha(x)-1)}{2}$.
To find the find the overall number of substrings of interest it suffices
to sum the above quantity over all choices of $x \in \{0,1\}^m$:
$$
\sum_{x \in \{0,1\}^m} \binom{\alpha(x)}{2} = \frac{1}{2} \sum_{x \in \{0,1\}^m} \alpha(x) (\alpha(x)-1).
$$
Since $m=O(1)$, all values of $\eta(i)$, for $i=0, \dots, n$ can be computed in $O(nm) = O(n)$ time. Moreover, all values of $\alpha(x)$ for $x \in \{0,1\}^m$ can also be found in $O(n m \log \min\{n, 2^m\}) = O(n)$ time by scanning $\eta(0), \dots, \eta(n)$ once and maintaining a counter for each $x$ (these counters can be stored in a dictionary with at most $\min\{n,2^m\}$ elements).
Finally, the final sum can be computed using $O(\min\{n, 2^m\}) = O(1)$ arithmetic operations (as it only needs to extend to $x \in \{0,1\}$ for which $\alpha(x) &gt; 0$).

An example implementation due to @orlp of the above in Python using a binary integer as the vector $x$ and storing all $a(x)$ in a hashmap counter is as follows:
def num_even_substrings(s):
    a = {0: 1}
    x = 0
    for c in s:
        x ^= 1 &lt;&lt; ord(c)
        a[x] = a.get(x, 0) + 1
    return sum(ax*(ax-1)//2 for ax in a.values())