Primer carácter único
La misión
Problema
Dado un texto, encuentra la posición del primer carácter que aparece exactamente una vez en todo el texto. Las posiciones se cuentan desde cero. Devuelve -1 cuando todos los caracteres aparecen más de una vez.
Ejemplos
Input: text = "reference"
Output: 2
Por qué: r y e se repiten más adelante, así que f es el primer carácter que está solo
Input: text = "aabb"
Output: -1
Por qué: cada carácter tiene un gemelo
Input: text = ""
Output: -1
Por qué: caso límite: no hay ningún carácter que reportar
Pistas
0 / 3
Que un carácter sea único depende de todo el texto, incluido lo que viene después de él, así que ninguna decisión de izquierda a derecha puede tomarse a primera vista.
Separa las dos preguntas: cuántas veces aparece cada carácter y qué posición va primero. La primera pregunta puede responderse por completo antes de plantear la segunda.
Cuenta cada carácter en una pasada. Luego recorre el texto otra vez en orden y devuelve la posición del primer carácter cuyo conteo sea uno. Si llegas al final sin encontrarlo, la respuesta es -1.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(k)
Solución
La unicidad no puede decidirse en una sola pasada hacia adelante, porque un carácter visto una vez todavía puede repetirse más tarde. Dos pasadas lo resuelven con limpieza: la primera arma un conteo de cada carácter, y la segunda recorre el texto en orden y se detiene en el primer carácter cuyo conteo es uno. Recorrer el texto, y no el conteo, es lo que hace que la respuesta sea la primera posición y no una cualquiera. El tiempo es O(n) y el espacio es O(k) para los caracteres distintos.
from collections import Counter
def first_unique_index(text):
counts = Counter(text) # one pass to tally every character
for i, ch in enumerate(text):
if counts[ch] == 1: # the earliest character with a tally of one
return i
return -1
print(first_unique_index("reference")) # -> 2
print(first_unique_index("aabb")) # -> -1
print(first_unique_index("")) # -> -1¿Lo que te frena es la idea y no el código? Conteo de frecuencias lo explica.