First Unique Character in a String

+10

Recibes una cadena s de letras minúsculas del inglés. Encuentra el primer carácter que aparece exactamente una vez en toda la cadena y devuelve su índice, contando 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 va a 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, las letras c y o aparecen dos veces, d tres veces y e una vez, en el índice 8. Pero y también aparece una vez, en el índice 4, y aparece primero, así que la respuesta es 4.

Entrada: s = "swiss"
Salida: 1
Explicación: En swiss, la letra s aparece tres veces. La letra w en el índice 1 aparece una vez, y lo mismo ocurre con i en el índice 2; la primera de ellas gana, así que la respuesta es 1.

Entrada: s = "aabbcc"
Salida: -1
Explicación: Cada letra de aabbcc aparece dos veces, así que ningún carácter es único y la respuesta es -1.

+17 pruebas ocultas al enviar

Para ir más allá

Los caracteres llegan de uno en uno desde un flujo, y después de cada uno debes indicar el primer carácter único hasta el momento. ¿Cómo mantendrías la respuesta actualizada?

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 mirada de izquierda a derecha no es suficiente. Primero cuenta cada letra; después, la segunda pasada puede 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

Recorre las posiciones de izquierda a derecha. Para la posición i, busca en toda la cadena otra posición j que tenga la misma letra. Si no hay ninguna, s[i] es única y, como recorres de izquierda a derecha, es la primera letra única: devuelve i. En coddycode, las posiciones 0 a 3 encuentran cada una una copia, y la posición 4, la y, no encuentra ninguna.

El recorrido debe abarcar toda la cadena, antes y después de i. Una copia anterior en la cadena descalifica la letra tanto como una posterior.

Detenerse en la primera copia ayuda con la mayoría de las cadenas, pero no con todas. Cuando cada letra aparece en una secuencia larga, como 2000 as, después 2000 bs y así sucesivamente, el recorrido de cada letra pasa por todas las secuencias anteriores antes de encontrar una copia. Para n = 5 × 10^4, eso supone más de mil millones de comparaciones, demasiado lento para las pruebas más grandes.

Algoritmo

Para cada índice i, de izquierda a derecha:
Recorre todos los índices j distintos de i y detente en el primero en el que 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, después escanea

Intuición

La fuerza bruta vuelve a preguntar «¿aparece esta letra en algún otro lugar?» para cada posición. En su lugar, cuenta una sola vez. Solo existen 26 letras, así que un arreglo de 26 contadores contiene todos los recuentos, con el índice 0 para a y el índice 25 para z. El índice de una letra es su código de carácter menos el código de a.

La primera pasada llena los contadores. Para coddycode, indican: c: 2, o: 2, d: 3, y: 1, e: 1. La segunda pasada recorre la cadena desde la izquierda y se detiene en la primera posición cuya letra tiene un recuento de 1. Esa es y en el índice 4. La segunda pasada tiene que recorrer la cadena, no los 26 contadores, porque la pregunta se refiere a la primera posición, no a la primera letra del alfabeto.

Ambas pasadas leen la cadena una vez, así que el tiempo es O(n). Los contadores siguen siendo 26, independientemente de la longitud de la cadena, por lo que el espacio adicional es O(1).

Algoritmo

Crea un arreglo 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 conteo 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

La mayoría de los errores se deben a decidir demasiado pronto o a recorrer lo incorrecto en la segunda pasada.

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, la b.
Devolver la letra en lugar de su índice, o devolver el índice comenzando desde 1. Lua y R cuentan desde 1, así que resta 1 antes de devolverlo.
Olvidar el caso -1. Una cadena como aabbcc no tiene ninguna letra única, y la función debe devolver un valor de todos modos después del bucle.
Usar el código del carácter sin modificar para indexar los contadores. a es 97, muy por fuera del límite de un arreglo de 26; primero resta el código de a.

Preguntas frecuentes4

¿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 cada una, así que el tiempo es O(n). Los 26 contadores ocupan el mismo espacio para cualquier longitud, por lo 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, comprueba las 26 letras y toma el índice más pequeño entre las 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 arreglo para contar las letras?

Con solo letras minúsculas, un arreglo de 26 contadores es más pequeño y rápido que un mapa hash. 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.

¿Por qué la segunda pasada recorre la cadena y no los recuentos?

Los recuentos solo indican qué letras son únicas, no dónde están. La respuesta es la letra única que aparece primero en la cadena, así que tienes que recorrer la cadena en orden y detenerte en la primera posición cuya letra tenga un recuento de 1.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "coddycode"

Esperado