Irreducible Anagrams

Editorial oficial (C++) 

Explicación

Primero, podemos considerar el caso en que $l = r$, es decir, la subcadena tiene longitud $1$. Un anagrama reducible requiere que la subcadena se parta en $k \geq 2$ segmentos, lo cual es imposible para longitud $1$. Así, una subcadena de longitud $1$ tiene un anagrama irreducible.

En los casos siguientes, $l \neq r$.

Consideramos el caso en que $s[l] \neq s[r]$. Podemos crear un anagrama en el que todas las ocurrencias de $s[r]$ están al frente, y el resto de la cadena sigue. Este es un anagrama irreducible. Podemos asegurarnos de que el último segmento no contenga ocurrencias de $s[r]$. Esto es posible porque todas las ocurrencias están al frente.

Para ilustrarlo, consideremos el escenario en que nuestra cadena es $\text{abbbb}$. Podemos crear el anagrama $\text{bbbba}$. Este anagrama es irreducible porque para incluir $\text{a}$, debemos usar la cadena entera, lo que muestra que no se puede reducir.

A continuación, consideramos el caso en que $s[l] = s[r]$. Que la subcadena tenga o no un anagrama irreducible varía de un caso a otro.

Empecemos por el caso en que la subcadena solo contiene un carácter distinto. Esto no tiene un anagrama irreducible porque su único anagrama es ella misma. Como su único anagrama es ella misma, cualesquiera segmentos que elijamos siempre serán anagramas entre sí, lo que significa que solo tiene un anagrama reducible.

De los ejemplos anteriores se ve que tener $t[l]=s[l]$ y/o $t[r]=s[r]$ no ayuda a crear un anagrama irreducible. Si esto ocurre, podemos partir la cadena en dos segmentos, uno de longitud uno en $l$ o en $r$, y otro con todo lo demás. Por ejemplo, $s=\text{abcca}$, $\text{aabcc}$ no es un anagrama irreducible porque podemos tener un segmento $[0, 0]$ y otro $[1, 4]$. Así, es óptimo tener $t[l]\neq s[l]$ Y $t[r]\neq s[r]$.

Consideremos el caso en que $s$ tiene dos caracteres distintos, y sea $t$ un anagrama irreducible de $s$. Además, sea $s[0] = \text{a}$. La misma explicación aplica cuando $s[0] = \text{b}$, pero las letras estarán intercambiadas ($\text{a}\to\text{b y b}\to\text{a}$).

Definamos $x$ como la posición más a la izquierda donde el número de $\text{b}$s en $s[0:x]$ es mayor o igual que el número de $\text{b}$s en $t[0:x]$. $x$ es la posición donde el número de $\text{b}$s en $s$ es igual al número de $\text{b}$s en $t$: cuanto más a la derecha se va, más $\text{b}$s se obtienen, así que la primera posición en que esta condición se cumple es cuando el número de $\text{b}$s es igual. Como solo tenemos dos caracteres distintos, el número de $\text{a}$s también debe ser el mismo. Si tenemos $x+1$ caracteres en total y un número de $\text{b}$s, que llamamos $n$, debemos tener $x + 1 - n \ \text{a}$s en ambas cadenas. Así, $s[0:x]$ y $t[0:x]$ también son anagramas: si hay el mismo número de $\text{a}$s en $s$ y $t$, y de $\text{b}$s en $s$ y $t$, entonces deben ser anagramas. Como el primer y el último carácter son iguales, lo que significa que el último carácter es $\text{a}$, sabemos que $x$ debe estar antes del último carácter, porque agregar una $\text{a}$ no ayuda a aumentar el conteo de $\text{b}$s. Esto implica la existencia de otro anagrama.

Dado que existe un anagrama en $[0:x]$, sabemos que $t$ es un anagrama reducible, una contradicción con lo que afirmamos antes. La subcadena restante también debe ser un anagrama porque el número de $\text{a}$s en $s$ y $t$ es igual, y el de $\text{b}$s en $s$ y $t$ también es igual. En esencia, es decir $\text{algún número} - \text{otro número} = \text{algún número} - \text{otro número}$, donde $\text{algún número}$ puede ser el número total de $\text{a}$s o $\text{b}$s, y $\text{otro número}$ puede ser el número de ese mismo carácter que había en $[0:x]$. El lado izquierdo y el lado derecho pueden representar $s$ y $t$.

El caso en que existen tres caracteres distintos es un poco más complicado. Para asegurar que el primer carácter de $s$ y de un anagrama sean distintos, podemos insertar al frente todas las ocurrencias del último carácter distinto en aparecer. Luego, para asegurar que el último carácter de $s$ y de un anagrama sean distintos, podemos insertar todas las ocurrencias del último carácter después del último carácter distinto, si son distintos (si son el mismo, no hace falta hacer nada). Ahora podemos insertar el resto de la cadena en cualquier orden. Este anagrama es irreducible. El último carácter de $s$ será uno de los primeros caracteres de $t$, lo que nos obliga a usar la cadena entera si queremos crear un anagrama.

Podemos generalizar estas observaciones: una cadena tiene al menos un anagrama irreducible si se cumple alguna de estas tres condiciones:

1. La cadena tiene tres o más caracteres distintos
2. El primer y el último carácter son distintos
3. La cadena tiene longitud 1

Las últimas dos condiciones son fáciles de comprobar. Sin embargo, para comprobar la primera, debemos usar sumas de prefijos. Para cada una de las 26 letras del alfabeto, podemos guardar una suma de prefijos que cuente cuántas veces se ha visto la letra. Si en un intervalo se han visto al menos una vez tres letras, entonces la cadena es un anagrama irreducible.

Implementación

Complejidad temporal: $\mathcal{O}(|s| + q)$ donde $|s|$ es la longitud de la cadena $s$ y $q$ es el número de consultas

#include <bits/stdc++.h>
 
using namespace std;
 
const int LETTERS = 26;
 
int main() {
	string s;
 
	cin >> s;
 
	vector<array<int, LETTERS>> pref(s.length() + 1);
 
	for (int i = 1; i < s.length() + 1; i++) {
		pref[i] = pref[i - 1];
 
		char let = s[i - 1];
		pref[i][let - 'a']++;
	}
 
	int t;
 
	cin >> t;
 
	while (t--) {
		int a, b;
		cin >> a >> b;
 
		int num_diff = 0;
 
		for (int i = 0; i < LETTERS; i++) {
			if (pref[b][i] - pref[a - 1][i] > 0) { num_diff++; }
		}
 
		if (b == a || num_diff >= 3 || s[a - 1] != s[b - 1]) {
			cout << "Yes" << "\n";
		} else {
			cout << "No" << "\n";
		}
	}
}