First Unique Character in a String

+10

Vous recevez une chaîne s composée de lettres minuscules anglaises. Trouvez le premier caractère qui apparaît exactement une fois dans toute la chaîne et renvoyez son indice, en commençant à compter à partir de 0. Si chaque caractère apparaît plus d’une fois, renvoyez -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 aucune

Contraintes

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

Exemples

Entrée: s = "coddycode"
Sortie: 4
Explication: Dans coddycode, les lettres c et o apparaissent deux fois, d trois fois et e une fois, à l’indice 8. Mais y apparaît aussi une fois, à l’indice 4, et il vient en premier, donc la réponse est 4.

Entrée: s = "swiss"
Sortie: 1
Explication: Dans swiss, la lettre s apparaît trois fois. La lettre w à l’index 1 apparaît une fois, tout comme i à l’index 2 ; la première l’emporte, donc la réponse est 1.

Entrée: s = "aabbcc"
Sortie: -1
Explication: Chaque lettre dans aabbcc apparaît deux fois, donc aucun caractère n’est unique et la réponse est -1.

+17 tests cachés à la soumission

Pour aller plus loin

Les caractères arrivent un par un depuis un flux, et après chacun, vous devez indiquer le premier caractère unique jusqu’à présent. Comment garderiez-vous la réponse à jour ?

Indices

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

0 sur 3 ouverts

Solution

Une lettre qui semble unique lorsque tu l’atteins peut se répéter tout à la fin de la chaîne : un simple balayage de gauche à droite ne suffit donc pas. Commence par compter chaque lettre ; le deuxième passage pourra ensuite déterminer en temps constant si chaque position contient une lettre unique.

Cherche une deuxième occurrence de chaque lettre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Parcours les positions de gauche à droite. Pour la position i, parcours toute la chaîne pour trouver une autre position j portant la même lettre. S’il n’y en a pas, s[i] est unique et, puisque tu avances de gauche à droite, c’est la première lettre unique : renvoie i. Dans coddycode, les positions 0 à 3 trouvent chacune une occurrence, et la position 4, le y, n’en trouve aucune.

Le parcours doit couvrir toute la chaîne, avant et après i. Une occurrence plus tôt dans la chaîne disqualifie la lettre tout autant qu’une occurrence plus tard.

S’arrêter à la première occurrence est utile pour la plupart des chaînes, mais pas pour toutes. Lorsque chaque lettre se trouve dans une longue séquence, comme 2000 a, puis 2000 b, et ainsi de suite, le parcours de chaque lettre passe devant toutes les séquences précédentes avant de trouver une occurrence. Pour n = 5 × 10^4, cela représente plus d’un milliard de comparaisons, ce qui est trop lent pour les tests les plus volumineux.

Algorithme

Pour chaque indice i, de gauche à droite :
Parcours chaque indice j autre que i, et arrête-toi au premier pour lequel s[j] est égal à s[i].
Si aucun j de ce type n’existe, retourne i.
Si chaque indice a trouvé une copie, retourne -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

La force brute demande « cette lettre apparaît-elle ailleurs ? » à nouveau pour chaque position. Compte une seule fois à la place. Il n’existe que 26 lettres, donc un tableau de 26 compteurs contient tous les décomptes, avec l’index 0 pour a et l’index 25 pour z. L’index d’une lettre correspond à son code de caractère moins le code de a.

Le premier passage remplit les compteurs. Pour coddycode, ils indiquent : c : 2, o : 2, d : 3, y : 1, e : 1. Le second passage parcourt la chaîne de gauche à droite et s’arrête à la première position dont la lettre a un décompte de 1. Il s’agit de y à l’index 4. Le second passage doit parcourir la chaîne, et non les 26 compteurs, car la question porte sur la première position, pas sur la première lettre de l’alphabet.

Les deux passages parcourent la chaîne une seule fois, donc la complexité temporelle est O(n). Le nombre de compteurs reste égal à 26, quelle que soit la longueur de la chaîne, donc l’espace supplémentaire est O(1).

Algorithme

Créez un tableau de 26 zéros.
Pour chaque lettre de s, ajoutez 1 à son compteur.
Parcourez de nouveau s à partir de l’index 0. Renvoyez le premier index dont la lettre a un compteur de 1.
Si le parcours se termine, renvoyez -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

La plupart des erreurs viennent d’une décision prise trop tôt ou du parcours du mauvais élément lors du second passage.

Vérifier uniquement les lettres avant la position i. Dans abca, le premier a n’a aucune occurrence avant lui, mais il n’est pas unique.
Parcourir le tableau de compteurs au lieu de la chaîne lors du second passage. Pour ba, le premier compteur égal à 1 correspond à a, mais la réponse est l’index 0, celui de b.
Renvoyer la lettre au lieu de son index, ou renvoyer l’index en base 1. Lua et R commencent à compter à partir de 1 ; il faut donc soustraire 1 avant de renvoyer la valeur.
Oublier le cas -1. Une chaîne comme aabbcc ne contient aucune lettre unique, et la fonction doit tout de même renvoyer une valeur après la boucle.
Indexer les compteurs à l’aide du code du caractère brut. a vaut 97, bien au-delà de la fin d’un tableau de 26 éléments ; il faut d’abord soustraire le code de a.

Questions fréquentes4

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 chacune, donc le temps est de O(n). Les 26 compteurs occupent le même espace quelle que soit la longueur, ce qui donne un espace supplémentaire de O(1).

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

Oui. En un seul passage, stockez pour chaque lettre l’index où elle apparaît pour la première fois, ou marquez-la comme répétée lorsqu’elle réapparaît. Vérifiez ensuite les 26 lettres et prenez le plus petit index parmi celles qui sont apparues une seule fois. La chaîne est parcourue une seule 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 qu’une table de hachage. 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.

Pourquoi le second passage parcourt-il la chaîne et non les comptages ?

Les comptages indiquent seulement quelles lettres sont uniques, pas où elles se trouvent. La réponse est la lettre unique qui apparaît en premier dans la chaîne ; il faut donc parcourir la chaîne dans l’ordre et s’arrêter à la première position dont la lettre a un comptage de 1.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "coddycode"

Attendu