First Unique Character in a String

+10

Ti viene data una stringa s composta da lettere minuscole dell'alfabeto inglese. Trova il primo carattere che compare esattamente una volta nell'intera stringa e restituisci il suo indice, contando da 0. Se ogni carattere compare più di una volta, restituisci -1.

Funzione

firstUniqChar(s: string) → integer

sstring: la stringa da cercare, solo lettere minuscole
Restituisceinteger: l'indice della prima lettera che compare esattamente una volta, oppure -1 se non ce n'è nessuna

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo lettere inglesi minuscole (da a a z).

Esempi

Input: s = "coddycode"
Output: 4
Spiegazione: In coddycode le lettere c e o compaiono due volte, d tre volte ed e una volta, all'indice 8. Ma anche y compare una volta, all'indice 4, e viene prima, quindi la risposta è 4.

Input: s = "swiss"
Output: 1
Spiegazione: In swiss la lettera s appare tre volte. La lettera w all’indice 1 appare una volta, e lo stesso vale per i all’indice 2; vince la prima, quindi la risposta è 1.

Input: s = "aabbcc"
Output: -1
Spiegazione: Ogni lettera in aabbcc compare due volte, quindi nessun carattere è unico e la risposta è -1.

+17 test nascosti all’invio

Per approfondire

I caratteri arrivano uno alla volta da un flusso e, dopo ciascuno, devi indicare il primo carattere univoco incontrato finora. Come manterresti aggiornata la risposta?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Una lettera che sembra unica quando la raggiungi può ripetersi proprio alla fine della stringa, quindi una sola occhiata da sinistra a destra non basta. Conta prima ogni lettera, poi il secondo passaggio può stabilire in tempo costante se ogni posizione contiene una lettera unica.

Cerca una seconda copia di ogni lettera

Corretto, ma non termina sui test più grandi

Intuizione

Esamina le posizioni da sinistra. Per la posizione i, scansiona l'intera stringa alla ricerca di un'altra posizione j con la stessa lettera. Se non ce n'è una, s[i] è unica e, poiché procedi da sinistra, è la prima lettera unica: restituisci i. In coddycode, nelle posizioni da 0 a 3 si trova ogni volta una copia, mentre alla posizione 4, la y, non se ne trova nessuna.

La scansione deve coprire l'intera stringa, sia prima che dopo i. Una copia precedente nella stringa squalifica la lettera tanto quanto una successiva.

Fermarsi alla prima copia è utile nella maggior parte delle stringhe, ma non in tutte. Quando ogni lettera si trova in una lunga sequenza, come 2000 a, poi 2000 b e così via, la scansione di ogni lettera percorre tutte le sequenze precedenti prima di trovare una copia. Per n = 5 × 10^4 si tratta di oltre un miliardo di confronti, troppi per i test più grandi.

Algoritmo

Per ogni indice i da sinistra a destra:
Esamina ogni indice j diverso da i e fermati al primo per cui s[j] è uguale a s[i].
Se non esiste un tale j, restituisci i.
Se per ogni indice è stata trovata una copia, restituisci -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

Conta le lettere, poi esegui la scansione

Intuizione

La forza bruta chiede «questa lettera compare in qualche altra posizione?» di nuovo per ogni posizione. Conta una sola volta, invece. Esistono solo 26 lettere, quindi un array di 26 contatori contiene tutti i conteggi, con l’indice 0 per a e l’indice 25 per z. L’indice di una lettera è il suo codice carattere meno il codice di a.

Il primo passaggio riempie i contatori. Per coddycode i conteggi sono: c: 2, o: 2, d: 3, y: 1, e: 1. Il secondo passaggio scorre la stringa da sinistra e si ferma alla prima posizione in cui la lettera ha un conteggio pari a 1. È y all’indice 4. Il secondo passaggio deve scorrere la stringa, non i 26 contatori, perché la domanda riguarda la prima posizione, non la prima lettera dell’alfabeto.

Entrambi i passaggi leggono la stringa una volta, quindi il tempo è O(n). I contatori restano 26, indipendentemente dalla lunghezza della stringa, quindi lo spazio aggiuntivo è O(1).

Algoritmo

Crea un array di 26 zeri.
Per ogni lettera di s, aggiungi 1 al suo contatore.
Percorri di nuovo s a partire dall'indice 0. Restituisci il primo indice la cui lettera ha un conteggio pari a 1.
Se la scansione termina, restituisci -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

Trappole e casi limite

La maggior parte degli errori deriva dal decidere troppo presto o dal percorrere la cosa sbagliata nel secondo passaggio.

Controllare solo le lettere prima della posizione i. In abca la prima a non ha copie prima di sé, eppure non è unica.
Percorrere l’array dei contatori invece della stringa nel secondo passaggio. Per ba, il primo contatore uguale a 1 corrisponde a a, ma la risposta è l’indice 0, cioè b.
Restituire la lettera invece del suo indice, oppure restituire l’indice con base 1. Lua e R contano a partire da 1, quindi sottrai 1 prima di restituire il valore.
Dimenticare il caso -1. Una stringa come aabbcc non ha lettere uniche, e la funzione deve comunque restituire un valore dopo il ciclo.
Usare il codice carattere grezzo per indicizzare i contatori. a è 97, ben oltre la fine di un array di 26 elementi; sottrai prima il codice di a.

Domande frequenti4

Qual è la complessità temporale di First Unique Character in a String?

Contare le lettere e poi scorrere la stringa richiede due passaggi di n passi ciascuno, quindi il tempo è O(n). I 26 contatori occupano lo stesso spazio per qualsiasi lunghezza, quindi lo spazio aggiuntivo è O(1).

Riesci a risolverlo con un’unica passata sulla stringa?

Sì. In un solo passaggio, memorizza per ogni lettera l’indice in cui è apparsa per la prima volta, oppure contrassegnala come ripetuta quando ricompare. Poi controlla le 26 lettere e prendi l’indice più piccolo tra quelle apparse una sola volta. La stringa viene letta una volta e il controllo finale richiede 26 passaggi.

È meglio usare una mappa hash o un array per contare le lettere?

Con sole lettere minuscole, un array di 26 contatori è più piccolo e veloce di una mappa hash. Una mappa hash è la scelta giusta quando la stringa può contenere qualsiasi carattere, come il testo Unicode. L’algoritmo rimane lo stesso: conta, poi esegui una scansione della stringa.

Perché il secondo passaggio scorre la stringa e non i conteggi?

I conteggi indicano solo quali lettere sono uniche, non dove si trovano. La risposta è la lettera unica che compare per prima nella stringa, quindi devi scorrere la stringa in ordine e fermarti alla prima posizione in cui la lettera ha un conteggio pari a 1.

Python

def firstUniqChar(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "coddycode"

Atteso