First Unique Character in a String

+10

Tu reçois une chaîne s composée de lettres minuscules de l’alphabet anglais. Trouve le premier caractère qui apparaît exactement une fois dans toute la chaîne et renvoie son indice, en comptant à partir de 0. Si chaque caractère apparaît plus d’une fois, renvoie -1.

Fonction

firstUniqChar(s: string) → integer

sstring: la chaîne à rechercher, uniquement des lettres minuscules
Renvoieinteger: l’indice de la première lettre qui apparaît exactement une fois, ou -1 s’il n’y en a pas

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s ne contient que des lettres anglaises minuscules (a à z).

Exemples

Entrée: s = "coddycode"
Sortie: 4
Explication: Dans coddycode, c et o apparaissent deux fois, et d trois fois. y (indice 4) et e (indice 8) apparaissent une fois chacun, et y vient en premier, donc la réponse est 4.

Entrée: s = "swiss"
Sortie: 1
Explication: La lettre s apparaît trois fois. w à l’index 1 et i à l’index 2 apparaissent une fois chacun, et w vient en premier.

Entrée: s = "aabbcc"
Sortie: -1
Explication: Chaque lettre dans aabbcc apparaît deux fois, donc la réponse est -1.

Pour aller plus loin

Les caractères arrivent un à un d’un flux. Comment signaleriez-vous le premier caractère unique rencontré jusqu’ici après chacun d’eux ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une lettre qui semble unique lorsque vous y arrivez peut se répéter tout à la fin de la chaîne, donc un seul balayage de gauche à droite ne suffit pas. Comptez d’abord chaque lettre, puis le deuxième passage peut déterminer en temps constant si chaque position contient une lettre unique.

Cherchez une deuxième occurrence de chaque lettre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Pour chaque position en partant de la gauche, parcourez toute la chaîne pour trouver une autre position contenant la même lettre. Examinez les deux côtés : une occurrence précédente disqualifie une lettre autant qu’une occurrence suivante. La première position sans copie est la réponse. Dans coddycode, les positions 0 à 3 trouvent chacune une copie, tandis que le y à l’index 4 n’en trouve aucune.

S’arrêter à la première copie n’aide pas lorsque chaque lettre se trouve dans une longue séquence, comme 2000 a, puis 2000 b, et ainsi de suite : chaque parcours passe devant toutes les séquences précédentes. Pour n = 5 × 10^4, cela représente plus d’un milliard de comparaisons.

Algorithme

Pour chaque indice i de gauche à droite :
Parcourez tous les indices j autres que i, et arrêtez-vous au premier pour lequel s[j] est égal à s[i].
Si aucun j de ce type n'existe, renvoyez i.
Si chaque indice a trouvé une copie, renvoyez -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

Comptez les lettres, puis parcourez

Intuition

Comptez chaque lettre une seule fois au lieu de refaire une recherche pour chaque position. Il n’existe que 26 lettres, donc 26 compteurs suffisent pour stocker tous les décomptes, indexés par le code de la lettre moins le code de a.

Le premier parcours remplit les compteurs ; pour coddycode, seuls y et e se retrouvent avec un compte de 1. Le second parcours parcourt la chaîne depuis la gauche et s’arrête à la première lettre dont le compte est 1, le y à l’index 4. Deux parcours de n étapes donnent un temps en O(n), et 26 compteurs représentent un espace en O(1) quelle que soit la longueur.

Algorithme

Crée un tableau de 26 zéros.
Pour chaque lettre de s, ajoute 1 à son compteur.
Parcours de nouveau s à partir de l’index 0. Retourne le premier index dont la lettre a un compteur égal à 1.
Si le parcours se termine, retourne -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

Pièges et cas limites

Vérifier uniquement les lettres précédant la position i. Dans abca, le premier a n’a aucune copie avant lui, et pourtant il n’est pas unique.
Parcourir le tableau de compteurs au lieu de la chaîne lors du deuxième passage. Pour ba, le premier compteur égal à 1 correspond à a, mais la réponse est l’indice 0.
Indexer les compteurs avec le code caractère brut. a vaut 97, bien au-delà des 26 compteurs.
Renvoyer la lettre au lieu de son indice, ou un indice commençant à 1 en Lua ou en R.

Questions fréquentes3

Quelle est la complexité temporelle de « First Unique Character in a String » ?

Compter les lettres puis parcourir la chaîne nécessite deux passes de n étapes, donc le temps est O(n). Les 26 compteurs occupent le même espace quelle que soit la longueur, donc l’espace supplémentaire est O(1).

Peux-tu le résoudre en un seul parcours de la chaîne ?

Oui. En un seul parcours, stocke pour chaque lettre l’indice de sa première apparition, ou marque-la comme répétée lorsqu’elle apparaît à nouveau. Prends ensuite le plus petit indice parmi les 26 lettres apparues une seule fois. La chaîne est parcourue une fois, et la vérification finale coûte 26 étapes.

Faut-il utiliser une table de hachage ou un tableau pour compter les lettres ?

Avec uniquement des lettres minuscules, un tableau de 26 compteurs est plus petit et plus rapide. Une table de hachage est le bon choix lorsque la chaîne peut contenir n’importe quel caractère, comme du texte Unicode. L’algorithme reste le même : compter, puis parcourir la chaîne.

def firstUniqChar(s):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

s = "coddycode"

Résultat attendu