LeetCode0761 - Special Binary String

Nombre y enunciado

Un Special Binary String (Cadena Binaria Especial) es un string compuesto únicamente por caracteres '0' y '1' que cumple las siguientes condiciones:

1. El número de caracteres '1' es igual al número de caracteres '0'.
2. Para cualquier prefijo del string, el número de caracteres '1' es mayor o igual al número de caracteres '0'.

Se nos permite realizar una operación: elegir dos subcadenas especiales consecutivas, no vacías, e intercambiarlas. Dos subcadenas son consecutivas si el final de la primera coincide inmediatamente con el inicio de la segunda. El objetivo es realizar cualquier cantidad de estos intercambios para obtener el string lexicográficamente más grande posible.

Problema original en LeetCode

---

Intuición

A primera vista, el problema de intercambiar subcadenas consecutivas para maximizar lexicográficamente el resultado parece complejo de modelar directamente sobre cadenas binarias. La clave para simplificar el problema radica en realizar una analogía matemática:

Si reemplazamos cada '1' por un paréntesis de apertura ( y cada '0' por un paréntesis de cierre ), las dos propiedades de un string binario especial se traducen exactamente en las reglas de una secuencia de paréntesis balanceada:

• La cantidad de ( es igual a la de ).
• En ningún prefijo hay más ) que (.

Además, dado que todo string especial empieza con '1' y termina con '0', podemos pensar en cada componente especial básico como un bloque rodeado por un par de paréntesis más externo que contiene a su vez otra secuencia balanceada (posiblemente vacía): ( ... ), lo que en binario equivale a 1 + especial_interno + 0.

Bajo esta perspectiva:

• Las subcadenas especiales consecutivas son hermanos dentro del árbol de anidamiento de los paréntesis.
• Intercambiar subcadenas consecutivas equivale a reordenar estos hermanos.
• Dado que queremos maximizar el string lexicográficamente (es decir, poner los '1' (() lo más a la izquierda posible y los '0' ()) lo más a la derecha), la estrategia óptima para reordenar un conjunto de subcadenas especiales hermanas es simplemente ordenarlas en orden descendente.

Esta estructura recursiva permite resolver el problema descomponiendo el string en sus componentes independientes de nivel superior, optimizando recursivamente el interior de cada componente, y luego ordenándolos de manera ávida (greedy).

---

Definición formal

Entrada:

• Un string de caracteres $S$ de longitud $N$ ($2\le N\le 50$), compuesto únicamente por '0' y '1', que se garantiza que es un string binario especial.

Salida:

• El string binario especial lexicográficamente más grande obtenido tras aplicar cualquier número de intercambios válidos de subcadenas especiales consecutivas.

Restricciones:

• $N$ es par (debido a la cantidad igual de ceros y unos).
• La entrada es siempre un string binario especial válido.

---

Ejemplo concreto

Tomemos el string binario especial $S=\text{"11011000"}$.

1. Descomposición de primer nivel: Comenzamos a recorrer de izquierda a derecha manteniendo un contador de balance (incrementado por '1', decrementado por '0').

   • S[0] = '1' (balance = 1)
   • S[1] = '1' (balance = 2)
   • S[2] = '0' (balance = 1)
   • S[3] = '1' (balance = 2)
   • S[4] = '1' (balance = 3)
   • S[5] = '0' (balance = 2)
   • S[6] = '0' (balance = 1)
   • S[7] = '0' (balance = 0) $\to$ Alcanzamos balance 0 al final.

   Esto significa que todo el string $S$ es una única subcadena especial en el nivel superior. Se expresa como: 1 + $S_{interno}$ + 0, donde $S_{interno}=\text{"101100"}$.

2. Resolución recursiva de $S_{interno}$: Analizamos $S_{interno}=\text{"101100"}$ y lo descomponemos en sus componentes de nivel superior:

   • S_int[0] = '1' (balance = 1)
   • S_int[1] = '0' (balance = 0) $\to$ Primer bloque especial: $A=\text{"10"}$.
   • S_int[2] = '1' (balance = 1)
   • S_int[3] = '1' (balance = 2)
   • S_int[4] = '0' (balance = 1)
   • S_int[5] = '0' (balance = 0) $\to$ Segundo bloque especial: $B=\text{"1100"}$.

   Tenemos dos subcadenas especiales consecutivas: $A=\text{"10"}$ y $B=\text{"1100"}$.

3. Llamadas recursivas para $A$ y $B$:

   • Para $A=\text{"10"}$, el interior es vacío $\to$ Retorna $\text{"10"}$.
   • Para $B=\text{"1100"}$, el interior es $\text{"10"}$. Al procesar el interior $\text{"10"}$, retorna $\text{"10"}$. Reconstruyendo $B$: 1 + $\text{"10"}$ + 0 = $\text{"1100"}$.

4. Combinación y reordenamiento de los bloques en $S_{interno}$: Tenemos los bloques procesados: $A=\text{"10"}$ y $B=\text{"1100"}$. Dado que son consecutivos y de nivel superior dentro de $S_{interno}$, podemos intercambiarlos. Para maximizar lexicográficamente, los ordenamos de forma descendente:

   • Comparación: $\text{"1100"}>\text{"10"}$.
   • Resultado ordenado: $\text{"1100"}+\text{"10"}=\text{"110010"}$.

5. Reconstrucción del nivel superior: Reconstruimos el resultado final envolviendo la versión óptima de $S_{interno}$ con el '1' inicial y '0' final correspondientes al nivel superior:

   • $\text{"1"}+\text{"110010"}+\text{"0"}=\text{"11100100"}$.

Resultado final: $\text{"11100100"}$.

---

Por dónde empezar

Para abordar este problema, es fundamental:

1. Entender la analogía de los paréntesis: Visualizar el string como un árbol de anidamiento de subcadenas balanceadas.
2. Definir el caso base de la recursión: Las cadenas vacías o cadenas de longitud 2 ($\text{"10"}$) no se pueden descomponer ni reordenar internamente.
3. Pensar en la estrategia Greedy: ¿Por qué ordenar de forma descendente las subcadenas especiales hijas garantiza que el string resultante sea el lexicográficamente más grande?
4. Contrastar con Fuerza Bruta: Para entender el impacto de la estructura de paréntesis, conviene implementar primero un Backtracking clásico que intente realizar todas las permutaciones posibles de subcadenas especiales consecutivas en cualquier parte del string y evalúe la ineficiencia exponencial que esto genera.

---

Soluciones disponibles

• 0761_special_binary_string-backtracking
• 0761_special_binary_string-recursivo-greedy