O Primeiro Caractere Que Aparece Apenas Uma Vez

Link da Questão: https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/

Conteúdo da Questão:

Em uma string s, encontree o primeiro caractere que aparece apenas uma vez. Se não houver, retorne um espaço em branco. A string s contém apenas letras minúsculas.

Exemplo:

s = "abaccdeff"
Retorne "b"

s = "" 
Retorne " "

Restrições:

0 <= s.length <= 50000

Análise da Questão

O objetivo é simples: encontrar o primeiro caractere que aparece uma única vez na string. A abordagem mais direta é usar uma tabela de hash para contar as ocorrências de cada caractere, correspondendo ao dicionário no Python.

No entanto, ainda há espaço para otimizações com o uso do dicionário.

Método 1: Tabela de Hash

1. Percorra cada caractere c na string s e use um dicionário para rastrear se a contagem de c é maior que 1.
2. Percorra a string s novamente e encontre o primeiro caractere com contagem igual a 1, retornando-o.

Fluxo de Algoritmo:

1. Inicialização: Crie um dicionário vazio chamado dic.
2. Contagem de Caracteres: Para cada caractere c em s:
3. Se c não está em dic, adicione c com o valor True, indiacndo que ocorreu uma vez.
4. Se c já está em dic, altere o valor de c para False, indicando mais de uma ocorrência.
5. Procura pelo Primeiro Caractere Único: Percorra cada caractere c em s e verifique se dic[c] é True. Se sim, retorne c.
6. Retorne " " se nenhum caractere único for encontrado.

Análise de Complexidade:

• Tempo: O(N), onde N é o comprimento de s. Dois percursos são feitos na string, e as operações de dicionário são O(1).
• Espaço: O(N), já que o dicionário pode armazenar até N caracteres.

Código

class Solution:
    def firstUniqChar(self, s: str) -> str:
        dic = {}
        for c in s:
            dic[c] = c not in dic
        for c in s:
            if dic[c]:
                return c
        return " "

Método 2: Tabela de Hash Ordenada

Uma tabela de hash ordenada mantém as entradas de acordo com a ordem de inserção. Isso permite que você procure o primeiro caractere único diretamente na ordem do dicionário, sem precisar percorrer toda a string novamente.

Este método é mais eficiente quando a string é muito longa e contém muitos caracteres repetidos.

Análise de Complxeidade:

• Tempo: O(N), onde N é o comprimento de s. Apenas um percurso na string e um na tabela de hash são necessários.
• Espaço: O(N), semelhante ao Método 1.

Código

class Solution:
    def firstUniqChar(self, s: str) -> str:
        dic = {}
        for c in s:
            dic[c] = c not in dic
        for k, v in dic.items():
            if v:
                return k
        return " "