First Unique Character in a String

+10

Você recebe uma string s composta por letras minúsculas do inglês. Encontre o primeiro caractere que aparece exatamente uma vez na string inteira e retorne seu índice, começando a contagem em 0. Se todos os caracteres aparecerem mais de uma vez, retorne -1.

Função

firstUniqChar(s: string) → integer

sstring: o texto a ser pesquisado, somente letras minúsculas
Retornainteger: o índice da primeira letra que aparece exatamente uma vez, ou -1 se não houver nenhuma

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém apenas letras minúsculas do inglês (a a z).

Exemplos

Entrada: s = "coddycode"
Saída: 4
Explicação: Em coddycode, as letras c e o aparecem duas vezes, d três vezes e e uma vez, no índice 8. Mas y também aparece uma vez, no índice 4, e vem primeiro, então a resposta é 4.

Entrada: s = "swiss"
Saída: 1
Explicação: Em swiss, a letra s aparece três vezes. A letra w no índice 1 aparece uma vez, assim como i no índice 2; a primeira delas vence, então a resposta é 1.

Entrada: s = "aabbcc"
Saída: -1
Explicação: Cada letra em aabbcc aparece duas vezes, então nenhum caractere é único e a resposta é -1.

+17 testes ocultos ao enviar

Para ir além

Os caracteres chegam um de cada vez de um fluxo e, após cada um, você deve informar o primeiro caractere único até então. Como manter a resposta atualizada?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma letra que parece única quando você chega a ela pode se repetir bem no final da string, então uma única olhada da esquerda para a direita não é suficiente. Conte todas as letras primeiro; então, na segunda passagem, será possível determinar em tempo constante se cada posição contém uma letra única.

Procure uma segunda cópia de cada letra

Correta, mas não termina nos maiores testes

Intuição

Percorra as posições da esquerda para a direita. Para a posição i, percorra a string inteira procurando outra posição j com a mesma letra. Se não houver nenhuma, s[i] é única e, como você percorre da esquerda para a direita, é a primeira letra única: retorne i. Em coddycode, as posições de 0 a 3 encontram uma cópia cada, e a posição 4, o y, não encontra nenhuma.

A busca deve abranger a string inteira, antes e depois de i. Uma cópia anterior na string desqualifica a letra tanto quanto uma cópia posterior.

Parar na primeira cópia ajuda na maioria das strings, mas não em todas. Quando cada letra aparece em uma sequência longa, como 2000 as, depois 2000 bs e assim por diante, a busca de cada letra passa por todas as sequências anteriores antes de encontrar uma cópia. Para n = 5 × 10^4, isso resulta em mais de um bilhão de comparações, lento demais para os maiores testes.

Algoritmo

Para cada índice i, da esquerda para a direita:
Percorra todos os índices j diferentes de i e pare no primeiro em que s[j] seja igual a s[i].
Se não existir nenhum j assim, retorne i.
Se todos os índices encontrarem uma cópia, retorne -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

Conte as letras e, em seguida, examine

Intuição

A força bruta pergunta “esta letra aparece em algum outro lugar?” novamente para cada posição. Em vez disso, conte uma vez. Existem apenas 26 letras, então um array de 26 contadores armazena todas as contagens, com o índice 0 para a e o índice 25 para z. O índice de uma letra é seu código de caractere menos o código de a.

A primeira passagem preenche os contadores. Para coddycode, eles indicam c: 2, o: 2, d: 3, y: 1, e: 1. A segunda passagem percorre a string da esquerda e para na primeira posição cuja letra tem uma contagem igual a 1. Essa é y no índice 4. A segunda passagem precisa percorrer a string, não os 26 contadores, porque a pergunta é sobre a primeira posição, não sobre a primeira letra do alfabeto.

As duas passagens leem a string uma vez, então o tempo é O(n). Os contadores continuam sendo 26, independentemente do tamanho da string, então o espaço extra é O(1).

Algoritmo

Crie um array de 26 zeros.
Para cada letra de s, adicione 1 ao seu contador.
Percorra s novamente a partir do índice 0. Retorne o primeiro índice cuja letra tenha contagem igual a 1.
Se o percurso terminar, retorne -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

Armadilhas e casos extremos

A maioria dos erros acontece por decidir cedo demais ou por percorrer a estrutura errada na segunda passagem.

Verificar apenas as letras antes da posição i. Em abca, o primeiro a não tem nenhuma cópia antes dele, mas não é único.
Percorrer o array de contadores em vez da string na segunda passagem. Em ba, o primeiro contador igual a 1 pertence a a, mas a resposta é o índice 0, o b.
Retornar a letra em vez do índice, ou retornar o índice começando em 1. Lua e R contam a partir de 1, então subtraia 1 antes de retornar.
Esquecer o caso -1. Uma string como aabbcc não tem nenhuma letra única, e a função ainda deve retornar um valor após o loop.
Indexar os contadores usando o código bruto do caractere. a é 97, muito além do fim de um array de 26 elementos; primeiro subtraia o código de a.

Perguntas frequentes4

Qual é a complexidade de tempo para encontrar o primeiro caractere exclusivo em uma string?

Contar as letras e depois percorrer a string são duas passagens de n etapas cada, então o tempo é O(n). Os 26 contadores ocupam o mesmo espaço para qualquer comprimento, o que torna o espaço extra O(1).

Você consegue resolver isso em uma única passagem pela string?

Sim. Em uma única passagem, armazene para cada letra o índice em que ela apareceu pela primeira vez ou marque-a como repetida quando aparecer novamente. Em seguida, verifique as 26 letras e escolha o menor índice entre aquelas que apareceram uma única vez. A string é lida uma vez, e a verificação final leva 26 etapas.

Você deve usar uma tabela hash ou um array para contar as letras?

Com apenas letras minúsculas, um array de 26 contadores é menor e mais rápido do que um mapa de hash. Um mapa de hash é a escolha certa quando a string pode conter qualquer caractere, como texto Unicode. O algoritmo continua o mesmo: contar e, em seguida, percorrer a string.

Por que a segunda passagem percorre a string e não as contagens?

As contagens apenas indicam quais letras são únicas, não onde elas estão. A resposta é a letra única que aparece primeiro na string, então você precisa percorrer a string em ordem e parar na primeira posição cuja letra tenha contagem igual a 1.

Python

def firstUniqChar(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "coddycode"

Esperado