Three Days Ago

Explicación

Un string es feliz si y solo si la cantidad de cada dígito en el string es divisible por 2. Representamos esta información con un entero $i$ y lo llamamos el estado de una subcadena. El $k$ -ésimo bit de $i$ es 1 si el dígito $k$ apareció un número impar de veces en el string, y 0 en caso contrario.

Recorremos todas las subcadenas $[0, j]$ para todo $j \leq |S|$ y usamos un mapa $\text{states}$ para contar cuántas veces ocurre un estado en esas subcadenas. Cualquier subcadena $[l, r]$ es feliz si los estados de $[0, l - 1]$ y $[0, r]$ son idénticos.

Para contar la cantidad de subcadenas felices, basta considerar todos los estados. Para cada estado que ocurrió $x$ veces, hay $\frac{x(x-1)}{2}$ formas de emparejar dos de ellos $[0, j_1]$ y $[0, j_2]$ para obtener una subcadena feliz $[j_1 - 1, j_2]$ . El número total de subcadenas felices es entonces $\sum_i^{2^{10}} \frac{\text{states}[i] \cdot (\text{states}[i] - 1)}{2}$ .

Implementación

Complejidad temporal: $\mathcal{O}(|S| + 2^D)$ , donde $D = 10$ es la cantidad de dígitos posibles en el string.

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	string S;
	cin >> S;
 
	// el estado actual
	int cur_state = 0;
	// states[i] := # de ocurrencias del estado i en las subcadenas [0, j]
	map<int, ll> states;
	states[cur_state]++;
 
	for (const char &digit : S) {
		// actualizamos la paridad del dígito actual
		cur_state ^= 1 << (digit - '0');
		// actualizamos el contador del estado
		states[cur_state]++;
	}
 
	ll ans = 0;
	for (auto &[_, ct] : states) { ans += ct * (ct - 1) / 2; }
 
	cout << ans << endl;
}


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();
 
		// el estado actual
		int curState = 0;
		// states[i] := # de ocurrencias del estado i en las subcadenas [0, j]
		long[] states = new long[1 << 10];
		states[curState]++;
 
		for (char digit : S.toCharArray()) {
			// actualizamos la paridad del dígito actual
			curState ^= 1 << (digit - '0');
			// actualizamos el contador del estado
			states[curState]++;
		}
 
		long ans = 0;
		for (int i = 0; i < (1 << 10); i++) { ans += states[i] * (states[i] - 1) / 2; }
 
		System.out.println(ans);
	}
}


S = input()
 
# el estado actual
cur_state = 0
# states[i] := # de ocurrencias del estado i en las subcadenas [0, j]
states = [0 for i in range(1 << 10)]
states[cur_state] += 1
 
for digit in S:
	# actualizamos la paridad del dígito actual
	cur_state ^= 1 << int(digit)
	# actualizamos el contador del estado
	states[cur_state] += 1
 
ans = 0
for ct in states:
	ans += ct * (ct - 1) // 2
 
print(ans)