First Unique Character in a String

+10

Recibes una cadena s formada por letras minúsculas del alfabeto inglés. Encuentra el primer carácter que aparece exactamente una vez en toda la cadena y devuelve su índice, empezando a contar desde 0. Si todos los caracteres aparecen más de una vez, devuelve -1.

Función

firstUniqChar(s: string) → integer

sstring: la cadena que se buscará, solo letras minúsculas
Devuelveinteger: el índice de la primera letra que aparece exactamente una vez, o -1 si no hay ninguna

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo letras minúsculas del inglés (a a z).

Ejemplos

Entrada: s = "coddycode"
Salida: 4
Explicación: En coddycode, c y o aparecen dos veces y d tres veces. Tanto y (índice 4) como e (índice 8) aparecen una vez, y y aparece primero, así que la respuesta es 4.

Entrada: s = "swiss"
Salida: 1
Explicación: La letra s aparece tres veces. Tanto w en el índice 1 como i en el índice 2 aparecen una vez, y w aparece primero.

Entrada: s = "aabbcc"
Salida: -1
Explicación: Cada letra de aabbcc aparece dos veces, así que la respuesta es -1.

Para ir más allá

Los caracteres llegan uno a uno desde un flujo. ¿Cómo informarías del primer carácter único hasta el momento después de cada uno?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una letra que parece única cuando llegas a ella puede repetirse al final de la cadena, así que una sola pasada de izquierda a derecha no es suficiente. Cuenta primero todas las letras; después, la segunda pasada podrá determinar en tiempo constante si cada posición contiene una letra única.

Busca una segunda copia de cada letra

Correcto, pero no termina con las pruebas más grandes

Intuición

Para cada posición desde la izquierda, recorre toda la cadena en busca de otra posición con la misma letra. Revisa ambos lados: una copia anterior descalifica una letra tanto como una posterior. La primera posición sin ninguna copia es la respuesta. En coddycode, las posiciones de 0 a 3 encuentran cada una una copia y la y del índice 4 no encuentra ninguna.

Detenerse en la primera copia no ayuda cuando cada letra aparece en una secuencia larga, como 2000 as, después 2000 bs y así sucesivamente: cada recorrido pasa por todas las secuencias anteriores. Con n = 5 × 10^4, eso supone más de mil millones de comparaciones.

Algoritmo

Para cada índice i, de izquierda a derecha:
Recorre todos los índices j distintos de i y detente en el primero donde s[j] sea igual a s[i].
Si no existe tal j, devuelve i.
Si todos los índices encontraron una copia, devuelve -1.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

Cuenta las letras y después escanea

Intuición

Cuenta cada letra una sola vez en lugar de volver a buscar cada posición. Solo existen 26 letras, así que 26 contadores almacenan todos los recuentos, indexados por el código de la letra menos el código de a.

La primera pasada llena los contadores; para coddycode, solo y y e terminan con un valor de 1. La segunda pasada recorre la cadena desde la izquierda y se detiene en la primera letra cuyo recuento es 1: la y en el índice 4. Dos pasadas de n pasos requieren un tiempo de O(n), y 26 contadores ocupan un espacio de O(1) para cualquier longitud.

Algoritmo

Crea un array de 26 ceros.
Por cada letra de s, suma 1 a su contador.
Recorre s de nuevo desde el índice 0. Devuelve el primer índice cuya letra tenga un contador de 1.
Si termina el recorrido, devuelve -1.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

Errores comunes y casos límite

Comprobar solo las letras anteriores a la posición i. En abca, la primera a no tiene ninguna copia antes, pero no es única.
Recorrer el arreglo de contadores en lugar de la cadena en la segunda pasada. Para ba, el primer contador igual a 1 corresponde a a, pero la respuesta es el índice 0.
Indexar los contadores usando el código de carácter sin procesar. a es 97, muy por encima del final de los 26 contadores.
Devolver la letra en lugar de su índice, o un índice basado en 1 en Lua o R.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de «First Unique Character in a String»?

Contar las letras y después recorrer la cadena son dos pasadas de n pasos, así que el tiempo es O(n). Los 26 contadores ocupan el mismo espacio para cualquier longitud, así que el espacio adicional es O(1).

¿Puedes resolverlo en una sola pasada por la cadena?

Sí. En una pasada, guarda para cada letra el índice donde apareció por primera vez, o márcala como repetida cuando vuelva a aparecer. Después, toma el índice más pequeño entre las 26 letras que aparecieron una sola vez. La cadena se lee una vez y la comprobación final cuesta 26 pasos.

¿Deberías usar un mapa hash o un array para contar las letras?

Con solo letras minúsculas, un arreglo de 26 contadores ocupa menos espacio y es más rápido. Un mapa hash es la opción adecuada cuando la cadena puede contener cualquier carácter, como texto Unicode. El algoritmo sigue siendo el mismo: contar y después recorrer la cadena.

def firstUniqChar(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "coddycode"

Salida Esperada