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, contando a partir de 0. Se todos os caracteres aparecerem mais de uma vez, retorne -1.

Função

firstUniqChar(s: string) → integer

sstring: a string a ser pesquisada, apenas 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, c e o aparecem duas vezes e d aparece três vezes. Tanto y (índice 4) quanto e (índice 8) aparecem uma vez, e y vem primeiro, então a resposta é 4.

Entrada: s = "swiss"
Saída: 1
Explicação: A letra s aparece três vezes. Tanto w no índice 1 quanto i no índice 2 aparecem uma vez, e w vem primeiro.

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

Para ir além

Os caracteres chegam um de cada vez de um fluxo. Como você informaria o primeiro caractere único até então após cada chegada?

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 até ela pode se repetir no final da string, então uma única olhada da esquerda para a direita não é suficiente. Conte cada letra primeiro; assim, a segunda passagem poderá 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

Para cada posição da esquerda, percorra a string inteira em busca de outra posição com a mesma letra. Verifique os dois lados: uma ocorrência anterior desqualifica uma letra tanto quanto uma posterior. A primeira posição sem outra ocorrência é a resposta. Em coddycode, as posições de 0 a 3 encontram uma ocorrência, e o y no índice 4 não encontra nenhuma.

Parar na primeira ocorrência não ajuda quando cada letra está em uma sequência longa, como 2000 as, depois 2000 bs e assim por diante: cada varredura passa por todas as sequências anteriores. Para n = 5 × 10^4, isso representa mais de um bilhão de comparações.

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, faça a varredura

Intuição

Conte cada letra uma vez, em vez de pesquisar novamente para cada posição. Existem apenas 26 letras, então 26 contadores armazenam todas as contagens, indexadas pelo código da letra menos o código de a.

A primeira passagem preenche os contadores; para coddycode, apenas y e e terminam com valor 1. A segunda passagem percorre a string da esquerda para a direita e para na primeira letra cuja contagem é 1, o y no índice 4. Duas passagens de n etapas resultam em tempo O(n), e 26 contadores ocupam espaço O(1) para qualquer tamanho.

Algoritmo

Crie um array com 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 uma contagem de 1.
Se a percorrida 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

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.
Indexar os contadores usando o código bruto do caractere. a é 97, muito além do fim dos 26 contadores.
Retornar a letra em vez do índice, ou um índice baseado em 1 em Lua ou R.

Perguntas frequentes3

Qual é a complexidade de tempo de First Unique Character in a String?

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

Você consegue resolver isso percorrendo a string uma única vez?

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. Depois, escolha o menor índice entre as 26 letras que apareceram uma única vez. A string é percorrida uma vez, e a verificação final custa 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. Um mapa de hash é a escolha certa quando a string pode conter qualquer caractere, como texto Unicode. O algoritmo permanece o mesmo: contar e, em seguida, percorrer a string.

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

Teste #1

Teste #2

Teste #3

Argumento

s = "coddycode"

Saída Esperada