Count a Character
Você recebe uma string s e uma única letra c. Retorne quantas vezes c aparece em s. A correspondência diferencia maiúsculas de minúsculas: B e b são caracteres diferentes, então apenas ocorrências exatas de c são contabilizadas.
Função
- sstring
- a sequência de letras em inglês a ser pesquisada
- cstring
- a letra que deve ser contada
- Retornainteger
- quantos caracteres de s são iguais a c
Restrições
1 ≤ s.length ≤ 5 × 104scontém apenas letras do alfabeto inglês (aaz,AaZ).cé exatamente uma letra do alfabeto inglês.
Exemplos
- Entrada
- s = "Mississippi"c = "s"
- Saída
- 4
- Explicação
Mississippitem umsnas posições 2, 3, 5 e 6, contando a partir de 0, então a resposta é 4.
- Entrada
- s = "Banana"c = "b"
- Saída
- 0
- Explicação
Bananacomeça com uma letraBmaiúscula, e a busca é por uma letrabminúscula. As duas são diferentes, então nada corresponde e a resposta é 0.
+18 testes ocultos ao enviar
Para ir além
E se c pudesse ser uma palavra com várias letras, como ss? Correspondências sobrepostas contam, e como seu loop muda?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Para saber quantas vezes
caparece, quais caracteres desvocê precisa observar?Compare cada caractere de
scomcexatamente como eles são. Letras maiúsculas e minúsculas são caracteres diferentes aqui.Mantenha um contador que comece em 0. Percorra a string uma vez e adicione 1 sempre que o caractere atual for igual a
c.
Solução
Cada caractere de s precisa ser analisado uma vez, porque qualquer um deles pode ser um c. O trabalho consiste em uma única passagem com um contador. Os detalhes que costumam confundir as pessoas são maiúsculas e minúsculas (uma letra maiúscula é um caractere diferente) e, em algumas linguagens, comparar um caractere com uma string de uma letra.
Exclua cada c e compare os comprimentos
Intuição
Crie uma cópia de s com todos os c removidos. Cada caractere removido deixa a cópia um caractere menor, então a diferença entre os dois comprimentos é exatamente o número de vezes que c apareceu. A maioria das linguagens tem uma função de substituição ou exclusão que faz essa remoção para você.
Para Mississippi e s, a cópia é Miiippi. São 7 caracteres, contra os 11 originais, então c apareceu 4 vezes. Com Banana e b, nada é removido porque o B maiúsculo não corresponde, e a diferença é 0.
O trabalho consiste em uma única passagem por s, então o tempo é O(n). O custo é a memória: a cópia pode ter o mesmo comprimento que s, o que requer O(n) de espaço extra, algo de que um contador não precisa.
Algoritmo
- Faça uma cópia de
sque deixe de fora todos os caracteres iguais ac. - Meça o comprimento de
se o comprimento da cópia. - Retorne o comprimento de
smenos o comprimento da cópia.
def countChar(s, c):
# Every c that disappears makes the string one character shorter.
without = s.replace(c, "")
return len(s) - len(without)Uma passagem com um contador
Intuição
Ignore a cópia e conte enquanto lê. Percorra s da esquerda para a direita com um contador que começa em 0 e some 1 sempre que o caractere atual for igual a c. A correspondência é determinada por igualdade simples, então uma letra maiúscula nunca corresponde a uma minúscula.
Para Mississippi, o contador aumenta nos índices 2, 3, 5 e 6 e termina em 4. Cada caractere é comparado uma vez, e nada mais é armazenado.
Isso resulta em tempo O(n) e espaço extra O(1): um contador e a letra-alvo. Não é possível fazer melhor em termos de tempo, porque um caractere ignorado poderia ser mais um c.
Algoritmo
- Leia a letra-alvo de
ce definacount = 0. - Percorra
sum caractere por vez. - Se o caractere for igual à letra-alvo, adicione 1 a
count. - Retorne
count.
def countChar(s, c):
count = 0
for ch in s:
if ch == c:
count += 1
return count
Armadilhas e casos extremos
O loop é curto, e os bugs se escondem na forma como os dois valores são comparados.
- Ignorar maiúsculas e minúsculas. Converter os dois lados para minúsculas faz com que
Bananaebretornem 1, mas a tarefa pede correspondências exatas, então a resposta é 0. - Comparar um caractere com uma string. Em Java, C, C++, C# e Go,
cchega como uma string, enquantos.charAt(i)ous[i]é um único caractere. Peguec[0](ouc.charAt(0)) uma vez antes do loop. - Comparar strings com
==em Java.String.valueOf(s.charAt(i)) == ccompara a identidade dos objetos e quase sempre é falso. Compare valores decharou useequals. - Chamar
strlen(s)na condição do loop em C. A função percorre a string inteira a cada etapa, então5 × 10^4caracteres custam cerca de2.5 × 10^9etapas. Em vez disso, pare no terminador'\0'.
Perguntas frequentes4
Como contar as ocorrências de um caractere em uma string?
Inicie um contador em 0 e percorra a string uma vez. Cada vez que o caractere atual for igual ao que você está procurando, adicione 1. Quando o loop terminar, o contador será a resposta, e a execução levará O(n) de tempo, com O(1) de memória extra.
A contagem de caracteres diferencia maiúsculas de minúsculas?
Neste problema, sim: B e b são caracteres diferentes, então Banana não contém b. Se você precisar de uma contagem que não diferencie maiúsculas de minúsculas, converta a string e a letra para minúsculas antes de compará-las.
Posso usar uma função de contagem integrada em uma entrevista?
Geralmente sim, desde que você consiga dizer qual é o custo. str.count do Python e funções semelhantes ainda leem a string inteira, então são O(n). Muitos entrevistadores então pedem que você escreva o loop por conta própria, então esteja preparado para mostrá-lo.
Como você contaria todos os caracteres de uma só vez?
Faça uma única passagem e mantenha uma contagem por caractere, em um mapa hash ou em um array de 52 contadores para as letras do alfabeto inglês. Depois dessa passagem, a contagem de qualquer letra pode ser obtida com uma única consulta. Esse é o melhor plano quando perguntam sobre várias letras da mesma string.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def countChar(s, c):
# Escreva o código aquiCaso 1
Caso 2
Entrada
s = "Mississippi" c = "s"
Esperado
4