Official Analysis

Explanation

A string is happy if and only if the number of each digit in the string is divisible by 2. Let's represent this information using an integer $i$ and call it the state of a substring. The $k$-th bit of $i$ is 1 if the digit $k$ occurred odd times in the string, and 0 otherwise.

We go through all substrings $[0, j]$ for all $j \leq |S|$ and use a map $\text{states}$ to count how many times a state occurs in those substrings. Any substring $[l, r]$ is happy if the states of $[0, l - 1]$ and $[0, r]$ are identical.

To count the number of all happy substrings, we just have to consider all states. For each state that occurred $x$ times, there are $\frac{x(x-1)}{2}$ ways to map any two of them $[0, j_1]$ and $[0, j_2]$ to get a happy substring $[j_1 - 1, j_2]$. The total number of all happy substrings is then $\sum_i^{2^{10}} \frac{\text{states}[i] \cdot (\text{states}[i] - 1)}{2}$.

Implementation

Time Complexity: $\mathcal{O}(|S| + 2^D)$, where $D = 10$ is the number of possible digits in the string.

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	string S;
	cin >> S;

	// the current state

Copy
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String S = br.readLine();

		// the current state
		int curState = 0;
		// states[i] := # of occurrences of state i in the substrings [0, j]

Copy
S = input()

# the current state
cur_state = 0
# states[i] := # of occurrences of state i in the substrings [0, j]
states = [0 for i in range(1 << 10)]
states[cur_state] += 1

for digit in S:
	# update the parity of the current digit