Primeiro caractere único
A missão
Problema
Dado um texto, encontre a posição do primeiro caractere que aparece exatamente uma vez no texto inteiro. As posições são contadas a partir de zero. Retorne -1 quando todos os caracteres aparecem mais de uma vez.
Exemplos
Input: text = "reference"
Output: 2
Por quê: tanto r quanto e se repetem depois, então f é o primeiro caractere que aparece sozinho
Input: text = "aabb"
Output: -1
Por quê: todo caractere tem um gêmeo
Input: text = ""
Output: -1
Por quê: edge case: não há caractere para informar
Dicas
0 / 3
Saber se um caractere é único depende do texto inteiro, incluindo o que vem depois dele, então nenhuma decisão da esquerda para a direita pode ser tomada à primeira vista.
Separe as duas perguntas: com que frequência cada caractere aparece e qual posição vem primeiro. A primeira pergunta pode ser respondida por completo antes de a segunda ser feita.
Conte todos os caracteres em uma passada. Depois, percorra o texto de novo, em ordem, e retorne a posição do primeiro caractere cuja contagem é um. Chegar ao fim sem encontrar nenhum significa que a resposta é -1.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(k)
Solução
A unicidade não pode ser decidida em uma única passada para a frente, porque um caractere visto uma vez ainda pode se repetir depois. Duas passadas resolvem isso de forma limpa: a primeira monta a contagem de cada caractere, e a segunda percorre o texto em ordem e para no primeiro caractere cuja contagem é um. Percorrer o texto, e não a contagem, é o que faz a resposta ser a primeira posição, e não uma posição qualquer. O tempo é O(n) e o espaço é O(k) para os caracteres distintos.
from collections import Counter
def first_unique_index(text):
counts = Counter(text) # one pass to tally every character
for i, ch in enumerate(text):
if counts[ch] == 1: # the earliest character with a tally of one
return i
return -1
print(first_unique_index("reference")) # -> 2
print(first_unique_index("aabb")) # -> -1
print(first_unique_index("")) # -> -1Travou na ideia, e não no código? Contagem de frequência explica isso.