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.
Función
- sstring
- la cadena de letras en inglés que se debe 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 los índices 2, 3, 5 y 6, así que la respuesta es 4.
- Entrada
- s = "Banana"c = "b"
- Salida
- 0
- Explicación
Bananaempieza con unaBmayúscula, y estás buscando unabminúscula. No hay ninguna coincidencia, así que la respuesta es 0.
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 tal como son. Las letras mayúsculas y minúsculas son caracteres diferentes aquí.Mantén un contador que comience en 0. Recorre la cadena una vez y suma 1 cada vez que el carácter actual sea igual a
c.
Solución
Cualquier carácter de s podría ser un c, así que miras cada uno una vez y cuentas las coincidencias. Fíjate en las mayúsculas y minúsculas: una letra mayúscula es un carácter diferente.
Elimina cada c y compara las longitudes
Intuición
Crea una copia de s sin ningún c. Cada eliminación hace que la copia tenga un carácter menos, así que la diferencia de longitud es la cantidad. Para Mississippi, la copia es Miiippi: 11 menos 7 es 4.
El tiempo es O(n), pero la copia requiere O(n) de memoria 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
Cuenta mientras lees en lugar de crear una copia. Un contador comienza en 0 y aumenta en 1 por cada carácter igual a c. La igualdad simple evita que una letra mayúscula coincida con una minúscula.
Cada carácter se compara una sola vez y solo se almacena el contador: tiempo O(n), espacio O(1). Ninguna solución supera el tiempo O(n), porque un carácter que omitas podría ser una c más.
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
- Ignorar mayúsculas y minúsculas. Convertir ambos lados a minúsculas hace que
Bananaconbdevuelva 1; la respuesta es 0. - Comparar un carácter con una cadena. En Java, C, C++, C# y Go,
cllega como una cadena, mientras ques[i]os.charAt(i)es un 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 da falso. Compara valores de tipochar. - Llamar a
strlen(s)en la condición del bucle en C. Vuelve a recorrer la cadena en cada paso, así que5 × 10^4caracteres cuestan alrededor de2.5 × 10^9pasos.
Preguntas frecuentes3
¿Cómo cuentas las apariciones de un carácter en una cadena?
Recorre la cadena una vez con un contador que empieza en 0 y suma 1 cada vez que el carácter actual coincide con el que quieres. Esto requiere un tiempo de O(n) y memoria adicional de O(1). Para contar sin distinguir entre mayúsculas y minúsculas, primero convierte tanto la cadena como la letra a minúsculas.
¿Puedo usar una función de conteo integrada en una entrevista?
Normalmente sí, siempre que puedas decir cuánto cuesta. str.count de Python y funciones similares siguen leyendo toda la cadena, así que son O(n). Prepárate para escribir el bucle si te lo pregunta el entrevistador.
¿Cómo contarías todos los caracteres a la vez?
Haz una pasada y lleva la cuenta de cada carácter en un mapa hash o en un arreglo de 52 contadores para las letras inglesas. Después de esa pasada, el recuento de cualquier letra se obtiene con una sola consulta. Usa esto cuando te pregunten 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.
def countChar(s, c):
# Escribe el código aquíPrueba #1
Prueba #2
Argumentos
s = "Mississippi" c = "s"
Salida Esperada
4