First Unique Character in a String

+10

Ricevi 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 (a–z).

Esempi

Input: s = "coddycode"
Output: 4
Spiegazione: In coddycode, c e o compaiono due volte e d tre volte. Sia y (indice 4) sia e (indice 8) compaiono una volta, e y viene prima, quindi la risposta è 4.

Input: s = "swiss"
Output: 1
Spiegazione: La lettera s appare tre volte. Sia w all'indice 1 sia i all'indice 2 appaiono una volta, e w viene prima.

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

Per approfondire

Un carattere alla volta arriva da uno stream. Come segnaleresti il primo carattere univoco finora dopo ogni arrivo?

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 singola 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

Per ogni posizione da sinistra, esamina l’intera stringa alla ricerca di un’altra posizione con la stessa lettera. Esamina entrambi i lati: una copia precedente esclude una lettera tanto quanto una successiva. La prima posizione senza copie è la risposta. In coddycode, le posizioni da 0 a 3 trovano ciascuna una copia, mentre la y all’indice 4 non ne trova nessuna.

Fermarsi alla prima copia non aiuta quando ogni lettera si trova in un’unica sequenza lunga, come 2000 a, poi 2000 b e così via: ogni scansione attraversa tutte le sequenze precedenti. Con n = 5 × 10^4 si supera il miliardo di confronti.

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 j del genere, 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 scansiona

Intuizione

Conta ogni lettera una sola volta invece di cercarla di nuovo per ogni posizione. Esistono solo 26 lettere, quindi 26 contatori contengono tutti i conteggi, indicizzati dal codice della lettera meno il codice di a.

Il primo passaggio riempie i contatori; per coddycode, solo y e e terminano con conteggio 1. Il secondo passaggio scorre la stringa da sinistra e si ferma alla prima lettera il cui conteggio è 1: la y all'indice 4. Due passaggi di n operazioni richiedono un tempo O(n), e 26 contatori occupano uno spazio O(1) per qualsiasi lunghezza.

Algoritmo

Crea un array di 26 zeri.
Per ogni lettera di s, aggiungi 1 al suo contatore.
Scorri 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

Controllare solo le lettere prima della posizione i. In abca la prima a non ha copie prima di sé, eppure non è unica.
Scorrere l'array dei contatori invece della stringa nel secondo passaggio. In ba, il primo contatore uguale a 1 appartiene a a, ma la risposta è l'indice 0.
Usare il codice carattere grezzo per indicizzare i contatori. a è 97, ben oltre la fine dei 26 contatori.
Restituire la lettera invece del suo indice, oppure un indice basato su 1 in Lua o R.

Domande frequenti3

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

Contare le lettere e poi scorrere la stringa sono due passaggi di n passi, 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 scansione della stringa?

Sì. In un'unica passata, memorizza per ogni lettera l'indice in cui è comparsa per la prima volta, oppure contrassegnala come ripetuta quando compare di nuovo. Poi prendi l'indice più piccolo tra le 26 lettere apparse una sola volta. La stringa viene letta una volta e il controllo finale richiede 26 passaggi.

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

Con sole lettere minuscole, un array di 26 contatori è più piccolo e veloce. Una mappa hash è la scelta giusta quando la stringa può contenere qualsiasi carattere, ad esempio testo Unicode. L'algoritmo resta lo stesso: conta, poi scorri la stringa.

def firstUniqChar(s):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

s = "coddycode"

Output atteso