Count a Character
Recibes una cadena s y una sola letra c. Devuelve cuántas veces aparece c en s. La coincidencia distingue entre mayúsculas y minúsculas: B y b son caracteres diferentes, así que solo cuentan las apariciones exactas de c.
Función
- sstring
- la cadena de letras inglesas que se va a buscar
- cstring
- la única letra que se debe contar
- Devuelveinteger
- cuántos caracteres de s son iguales a c
Restricciones
1 ≤ s.length ≤ 5 × 104scontiene solo letras inglesas (aaz,AaZ).ces exactamente una letra inglesa.
Ejemplos
- Entrada
- s = "Mississippi"c = "s"
- Salida
- 4
- Explicación
Mississippitiene unasen las posiciones 2, 3, 5 y 6, contando desde 0, así que la respuesta es 4.
- Entrada
- s = "Banana"c = "b"
- Salida
- 0
- Explicación
Bananaempieza con unaBmayúscula, y la búsqueda es de unabminúscula. Son diferentes, así que no hay coincidencias y la respuesta es 0.
+18 pruebas ocultas al enviar
Para ir más allá
¿Qué pasaría si c pudiera ser una palabra de varias letras, como ss? ¿Cuentan las coincidencias superpuestas y cómo cambia tu bucle?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Para saber cuántas veces aparece
c, ¿qué caracteres desnecesitas mirar?Compara cada carácter de
sconcexactamente como están. Aquí, las letras mayúsculas y minúsculas son caracteres diferentes.Mantén un contador que empiece en 0. Recorre la cadena una vez y suma 1 cada vez que el carácter actual sea igual a
c.
Solución
Hay que revisar cada carácter de s una vez, porque cualquiera de ellos podría ser una c. El trabajo consiste en una sola pasada con un contador. Los detalles que suelen confundir son las mayúsculas (una letra mayúscula es un carácter diferente) y, en algunos lenguajes, comparar un carácter con una cadena de un solo carácter.
Elimina cada c y compara las longitudes
Intuición
Crea una copia de s en la que se haya eliminado cada c. Cada carácter eliminado hace que la copia sea un carácter más corta, así que la diferencia entre las dos longitudes es exactamente el número de veces que apareció c. La mayoría de los lenguajes tienen una función de reemplazo o eliminación que realiza esa operación por ti.
Para Mississippi y s, la copia es Miiippi. Tiene 7 caracteres frente a los 11 del original, así que c apareció 4 veces. Con Banana y b, no se elimina nada porque la B mayúscula no coincide, y la diferencia es 0.
El trabajo consiste en recorrer s una sola vez, así que el tiempo es O(n). El coste es la memoria: la copia puede ser tan larga como s, lo que supone O(n) de espacio adicional que un contador no necesita.
Algoritmo
- Haz una copia de
sque omita todos los caracteres iguales ac. - Mide la longitud de
sy la longitud de la copia. - Devuelve la longitud de
smenos la longitud de la copia.
def countChar(s, c):
# Every c that disappears makes the string one character shorter.
without = s.replace(c, "")
return len(s) - len(without)Una pasada con un contador
Intuición
Omite la copia y el conteo mientras lees. Recorre s de izquierda a derecha con un contador que empieza en 0 y súmale 1 cada vez que el carácter actual sea igual a c. La coincidencia se determina mediante igualdad simple, así que una letra mayúscula nunca coincide con una minúscula.
Para Mississippi, el contador aumenta en los índices 2, 3, 5 y 6, y termina en 4. Cada carácter se compara una vez y no se almacena nada más.
Eso da un tiempo O(n) y un espacio adicional O(1): un contador y la letra objetivo. No puedes mejorar el tiempo, porque un carácter que omitas podría ser otro c.
Algoritmo
- Lee la letra objetivo de
cy establececount = 0. - Recorre
sun carácter a la vez. - Si el carácter coincide con el objetivo, suma 1 a
count. - Devuelve
count.
def countChar(s, c):
count = 0
for ch in s:
if ch == c:
count += 1
return count
Errores comunes y casos límite
El bucle es corto, y los errores se esconden en la forma de comparar los dos valores.
- Ignorar las mayúsculas y minúsculas. Convertir ambos lados a minúsculas hace que
Bananaconbdevuelva 1, pero la tarea pide coincidencias exactas, así que la respuesta es 0. - Comparar un carácter con una cadena. En Java, C, C++, C# y Go,
cllega como una cadena, mientras ques.charAt(i)os[i]es un único carácter. Tomac[0](oc.charAt(0)) una vez antes del bucle. - Comparar cadenas con
==en Java.String.valueOf(s.charAt(i)) == ccompara la identidad de los objetos y casi siempre es falso. Compara valorescharo usaequals. - Llamar a
strlen(s)en la condición del bucle en C. Recorre toda la cadena en cada paso, por lo que5 × 10^4caracteres cuestan alrededor de2.5 × 10^9pasos. Detente en el terminador'\0'en su lugar.
Preguntas frecuentes4
¿Cómo cuentas las apariciones de un carácter en una cadena?
Inicia un contador en 0 y recorre la cadena una vez. Cada vez que el carácter actual sea igual al que buscas, suma 1. Cuando termine el bucle, el contador será la respuesta, y la ejecución tardará O(n) y usará O(1) de memoria adicional.
¿La cuenta de caracteres distingue entre mayúsculas y minúsculas?
En este problema, sí: B y b son caracteres diferentes, así que Banana no contiene ninguna b. Si necesitas un recuento que no distinga entre mayúsculas y minúsculas, convierte tanto la cadena como la letra a minúsculas antes de compararlas.
¿Puedo usar una función de conteo integrada en una entrevista?
Por lo general, sí, siempre que puedas explicar cuánto cuesta. str.count de Python y funciones similares siguen leyendo toda la cadena, así que son O(n). Muchos entrevistadores después te piden que escribas el bucle tú mismo, así que prepárate para mostrarlo.
¿Cómo contarías todos los caracteres a la vez?
Haz una pasada y lleva un recuento por carácter, en un mapa hash o en una matriz de 52 contadores para las letras inglesas. Después de esa pasada, el recuento de cualquier letra se obtiene con una sola consulta. Este es el mejor plan cuando te preguntan por muchas letras de la misma cadena.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def countChar(s, c):
# Escribe el código aquíCaso 1
Caso 2
Entrada
s = "Mississippi" c = "s"
Esperado
4