Count a Character

Q: Le comptage d’un caractère tient-il compte de la casse ?

Dans ce problème, oui : B et b sont des caractères différents, donc Banana ne contient pas de b . Si tu as plutôt besoin d’un comptage insensible à la casse, convertis la chaîne et la lettre en minuscules avant de les comparer.

Q: Peut-on utiliser une fonction de comptage intégrée lors d’un entretien ?

Généralement, oui, tant que tu peux expliquer son coût. str.count et les fonctions similaires de Python parcourent toujours toute la chaîne, donc leur complexité est O(n) . De nombreux recruteurs te demandent ensuite d’écrire toi-même la boucle, alors prépare-toi à la montrer.

DébutantTableaux et chaînes

+10

Tu reçois une chaîne de caractères s et une seule lettre c. Retourne le nombre de fois où c apparaît dans s. La correspondance est sensible à la casse : B et b sont des caractères différents, donc seules les occurrences exactes de c sont comptées.

Fonction

countChar(s: string, c: string) → integer

sstring: la chaîne de lettres anglaises à rechercher
cstring: la lettre à compter
Renvoieinteger: combien de caractères de s sont égaux à c

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s ne contient que des lettres de l’alphabet anglais (a à z, A à Z).
c est exactement une lettre anglaise.

Exemples

Entrée: s = "Mississippi"c = "s"
Sortie: 4
Explication: Mississippi contient un s aux positions 2, 3, 5 et 6, en comptant à partir de 0, donc la réponse est 4.

Entrée: s = "Banana"c = "b"
Sortie: 0
Explication: Banana commence par un B majuscule, et la recherche porte sur un b minuscule. Les deux sont différents, donc rien ne correspond et la réponse est 0.

+18 tests cachés à la soumission

Pour aller plus loin

Et si c pouvait être un mot de plusieurs lettres, comme ss ? Les correspondances qui se chevauchent comptent-elles, et comment ta boucle change-t-elle ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque caractère de s doit être examiné une fois, car n’importe lequel peut être un c. Le travail consiste à effectuer un seul parcours avec un compteur. Les détails qui posent problème sont la casse (une majuscule est un caractère différent) et, dans certains langages, la comparaison d’un caractère avec une chaîne d’un seul caractère.

Supprime chaque c et compare les longueurs

Intuition

Crée une copie de s en supprimant chaque c. Chaque caractère supprimé raccourcit la copie d’un caractère, donc la différence entre les deux longueurs correspond exactement au nombre d’occurrences de c. La plupart des langages disposent d’une fonction de remplacement ou de suppression qui effectue cette opération à ta place.

Pour Mississippi et s, la copie est Miiippi. Elle comporte 7 caractères, contre 11 pour l’original, donc c apparaît 4 fois. Avec Banana et b, rien n’est supprimé, car le B majuscule ne correspond pas, et la différence est de 0.

Le traitement consiste en un seul passage sur s, donc sa durée est O(n). Le coût concerne la mémoire : la copie peut être aussi longue que s, ce qui représente un espace supplémentaire de O(n) dont un compteur n’a pas besoin.

Algorithme

Faites une copie de s en omettant chaque caractère égal à c.
Mesurez la longueur de s et celle de la copie.
Renvoyez la longueur de s moins celle de la copie.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

Un seul passage avec un compteur

Intuition

Évitez la copie et faites le décompte au fur et à mesure. Parcourez s de gauche à droite avec un compteur qui commence à 0, et ajoutez 1 chaque fois que le caractère actuel est égal à c. La comparaison se fait par égalité simple : une majuscule ne correspond jamais à une minuscule.

Pour Mississippi, le compteur augmente aux indices 2, 3, 5 et 6 et atteint 4 à la fin. Chaque caractère est comparé une fois, et rien d’autre n’est stocké.

Cela donne un temps de O(n) et un espace supplémentaire de O(1) : un compteur et la lettre cible. Vous ne pouvez pas faire mieux en temps, car un caractère ignoré pourrait être un autre c.

Algorithme

Lisez la lettre cible depuis c et définissez count = 0.
Parcourez s caractère par caractère.
Si le caractère est égal à la cible, ajoutez 1 à count.
Retournez count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

Pièges et cas limites

La boucle est courte, et les bogues se cachent dans la façon dont les deux valeurs sont comparées.

Ignorer la casse. Mettre les deux côtés en minuscules fait renvoyer 1 pour Banana et b, mais la tâche demande des correspondances exactes : la réponse est donc 0.
Comparer un caractère à une chaîne. En Java, C, C++, C# et Go, c est une chaîne, tandis que s.charAt(i) ou s[i] est un caractère unique. Récupérez c[0] (ou c.charAt(0)) une fois avant la boucle.
Comparer des chaînes avec == en Java. String.valueOf(s.charAt(i)) == c compare l’identité des objets et renvoie presque toujours false. Comparez des valeurs de type char, ou utilisez equals.
Appeler strlen(s) dans la condition de boucle en C. La fonction parcourt toute la chaîne à chaque étape : 5 × 10^4 caractères coûtent donc environ 2.5 × 10^9 étapes. Arrêtez-vous plutôt au terminateur '\0'.

Questions fréquentes4

Comment compter le nombre d’occurrences d’un caractère dans une chaîne de caractères ?

Initialisez un compteur à 0 et parcourez la chaîne une fois. Chaque fois que le caractère courant est égal à celui que vous recherchez, ajoutez 1. Lorsque la boucle se termine, le compteur correspond à la réponse, et l’exécution prend un temps de O(n) avec une mémoire supplémentaire de O(1).

Le comptage d’un caractère tient-il compte de la casse ?

Dans ce problème, oui : B et b sont des caractères différents, donc Banana ne contient pas de b. Si tu as plutôt besoin d’un comptage insensible à la casse, convertis la chaîne et la lettre en minuscules avant de les comparer.

Peut-on utiliser une fonction de comptage intégrée lors d’un entretien ?

Généralement, oui, tant que tu peux expliquer son coût. str.count et les fonctions similaires de Python parcourent toujours toute la chaîne, donc leur complexité est O(n). De nombreux recruteurs te demandent ensuite d’écrire toi-même la boucle, alors prépare-toi à la montrer.

Comment compteriez-vous tous les caractères d’un seul coup ?

Parcourez la chaîne une fois et comptabilisez chaque caractère dans une table de hachage ou dans un tableau de 52 compteurs pour les lettres anglaises. Après ce parcours, le nombre d’occurrences de n’importe quelle lettre s’obtient en une seule recherche. C’est la meilleure approche lorsqu’on vous interroge sur plusieurs lettres d’une même chaîne.

Python

def countChar(s, c):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

s = "Mississippi"
c = "s"

Attendu