Counting Reorders

Calcular el número de formas en que se pueden reordenar los caracteres de un string de modo que no haya dos caracteres adyacentes iguales.

Estrategia: inclusión-exclusión

La restricción “ningún par de caracteres adyacentes son iguales” es difícil de contar de forma directa. En su lugar, usamos el principio de inclusión-exclusión (PIE) para transformar el problema en contar arreglos con un número específico de conexiones “malas”.

Definir “pares malos”

Sea un par malo una instancia en la que dos caracteres idénticos se colocan uno al lado del otro (p. ej., AA). Queremos encontrar el número de arreglos con exactamente cero pares malos.

En lugar de contar “exactamente cero” de forma directa, PIE nos dice que contemos arreglos en los que hemos forzado $K$ adyacencias específicas a ser malas. La fórmula para arreglos con cero pares malos es:

\sum_{K=0}^{n-1} (-1)^K \times (\text{Ways to force } K \text{ Bad Pairs})

Por qué funciona

Cuando forzamos $K$ adyacencias, no estamos diciendo que el string tenga solo $K$ pares malos; podría tener más. Sin embargo, el signo alternado $(-1)^K$ asegura que cualquier arreglo que realmente contenga $m$ pares malos (donde $m > 0$ ) se cuente un total de:

\sum_{k=0}^{m} \binom{m}{k}(-1)^k = (1-1)^m = 0 \text{ times}

Esto deja solo los arreglos con cero pares malos en nuestra suma final, cada uno contado exactamente una vez.

Conectar PIE con segmentos

Para calcular las “formas de forzar $K$ pares malos”, tratamos cada adyacencia forzada como un “enlace” que fusiona dos caracteres idénticos en un único bloque. Si tenemos un string de longitud total $n$ y usamos $K$ enlaces para forzar adyacencias, nos quedan $i$ segmentos independientes:

i = n - K \quad \text{or} \quad K = n - i

Esto motiva nuestra programación dinámica: si podemos contar cuántas formas hay de formar exactamente $i$ segmentos, podemos aplicar el signo de PIE $(-1)^{n-i}$ a ese conteo para llegar a nuestra respuesta final.

Explicación paso a paso

1. Preprocesamiento

Contamos la frecuencia f de cada carácter. También precomputamos coeficientes binomiales $\binom{n}{r}$ usando la lógica del triángulo de Pascal. Esto nos permite acceder a combinaciones en tiempo $\mathcal{O}(1)$ mientras procesamos la DP.

2. El estado de programación dinámica

Definimos un estado de DP $dp[i][j]$

i: hemos procesado los primeros i tipos de caracteres distintos.
j: el número total de segmentos formados por estos caracteres.

3. La transición

Al introducir un nuevo carácter con frecuencia f, decidimos partirlo en k segmentos ( $1 \le k \le f$ ). Esta transición involucra:

Partir los caracteres: formas de dividir f ítems idénticos en k segmentos no vacíos (problema de estrellas y barras): $\binom{f - 1}{k - 1}$
Fusionar con segmentos existentes: formas de intercalar estos k segmentos nuevos entre los j segmentos ya procesados: $\binom{j+k}{k}$

La regla de actualización:

dp[i][j+k] += dp[i-1][j] \times \binom{f-1}{k-1} \times \binom{j+k}{k}

4. Simplificación final de paridad

Después de procesar todos los grupos de caracteres, agregamos los valores en dp[groups][i] usando el signo de PIE $(-1)^{n-i}$ . El signo depende de la paridad de $n-i$ :

Si $n-i$ es par, el signo es positivo (+).
Si $n-i$ es impar, el signo es negativo (-).

Esto es equivalente a verificar si $(n + i)$ es par: if ((i + n) % 2 == 0).

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++Python


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll MOD = 1e9 + 7;
const int MAX_N = 5005;
const int ALPH = 26;
 
ll nCr[MAX_N][MAX_N];    // Binomial coefficients table
ll dp[ALPH + 3][MAX_N];  // dp[i][j]: i-th char group, j total segments
ll freq[ALPH];           // Frequency of each character
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	string s;
	cin >> s;
	int n = s.size();
 
	// 1. Count Frequencies
	for (char c : s) freq[c - 'a']++;
 
	// Filter out characters that don't appear in the string
	vector<int> counts;
	counts.push_back(0);  // Dummy 0-index
	for (int i = 0; i < ALPH; i++)
		if (freq[i]) counts.push_back(freq[i]);
 
	// 2. Precompute nCr (Pascal's Triangle)
	nCr[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		nCr[i][0] = 1;
		for (int j = 1; j <= n; j++)
			nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % MOD;
	}
 
	// 3. Dynamic Programming
	dp[0][0] = 1;
	int used_len = 0;  // Tracks number of segments processed so far
 
	for (int i = 1; i < (int)counts.size(); i++) {
		int f = counts[i];  // Frequency of current char
 
		// Iterate over previous number of segments (j)
		for (int j = 0; j <= used_len; j++) {
			// Iterate over how many segments (k) we split the current char into
			for (int k = 1; k <= f; k++) {
 
				ll ways = dp[i - 1][j];
 
				// Ways to split frequency f into k parts
				ways = (ways * nCr[f - 1][k - 1]) % MOD;
 
				// Ways to interleave k new parts into j existing parts
				ways = (ways * nCr[j + k][k]) % MOD;
 
				// Update DP state
				dp[i][j + k] = (dp[i][j + k] + ways) % MOD;
			}
		}
		used_len += f;
	}
 
	// 4. Inclusion-Exclusion
	ll answer = 0;
	int groups = counts.size() - 1;
 
	for (int i = 0; i <= n; i++) {
		// Apply PIE based on parity
		if ((i + n) % 2 == 0) answer = (answer + dp[groups][i]) % MOD;
		else answer = (answer - dp[groups][i] + MOD) % MOD;
	}
 
	cout << answer << '\n';
	return 0;
}


import sys
 
MOD = 10**9 + 7
MAX_N = 5005
ALPH = 26
 
s = sys.stdin.readline().strip()
n = len(s)
 
# frequency of each character
freq = [0] * ALPH
for c in s:
	freq[ord(c) - ord("a")] += 1
 
# keep only non-zero frequencies
counts = [0]
for f in freq:
	if f:
		counts.append(f)
 
# precompute binomial coefficients (Pascal triangle)
nCr = [[0] * (n + 1) for _ in range(n + 1)]
nCr[0][0] = 1
 
for i in range(1, n + 1):
	nCr[i][0] = 1
	for j in range(1, i + 1):
		nCr[i][j] = (nCr[i - 1][j - 1] + nCr[i - 1][j]) % MOD
 
# dp[i][j] = ways using first i characters to form length j
dp = [[0] * (n + 1) for _ in range(len(counts))]
dp[0][0] = 1
 
used_len = 0
 
# process each character group
for i in range(1, len(counts)):
	f = counts[i]
 
	for j in range(used_len + 1):
		if dp[i - 1][j] == 0:
			continue
 
		for k in range(1, f + 1):
			ways = dp[i - 1][j] * nCr[f - 1][k - 1] % MOD * nCr[j + k][k] % MOD
			dp[i][j + k] = (dp[i][j + k] + ways) % MOD
 
	used_len += f
 
# inclusion-exclusion by parity
answer = 0
groups = len(counts) - 1
 
for i in range(n + 1):
	if (i + n) % 2 == 0:
		answer = (answer + dp[groups][i]) % MOD
	else:
		answer = (answer - dp[groups][i]) % MOD
 
print(answer % MOD)