Nota de rescate con letras de revista
La misión
Problema
Un rotulista recorta letras de una pancarta sobrante para escribir un mensaje nuevo. Dados dos strings (cadenas) en minúsculas note y banner, devuelve True si note se puede escribir con letras de banner, donde cada letra de banner se puede usar como máximo una vez. Ambos strings tienen hasta 100 000 letras, así que evita volver a buscar en la pancarta por cada letra de la nota.
Ejemplos
Input: note = "aab", banner = "baa"
Output: True
Por qué: la pancarta tiene dos a y una b, justo lo que necesita la nota
Input: note = "aa", banner = "ab"
Output: False
Por qué: la nota necesita dos a y la pancarta solo tiene una
Input: note = "", banner = "xyz"
Output: True
Por qué: caso límite: una nota vacía no necesita ninguna letra
Pistas
0 / 3
Aquí el orden no importa, solo cuántas tienes de cada letra. ¿Qué única tabla resumiría la pancarta?
Cuenta cada letra de la pancarta una vez. Después, cada letra de la nota es un retiro de ese conteo.
Recorre la nota y resta uno al conteo de cada letra. Si un conteo fuera a bajar de cero, a la pancarta se le acabó esa letra, así que devuelve False.
- Tiempo objetivo
- O(n + m)
- Espacio objetivo
- O(1)
Restricciones
- note and banner are lowercase letters
- each string has at most 10⁵ letters
Solución
Solo importa la cantidad de copias de cada letra, así que la pancarta se reduce en una pasada a una tabla de conteos de letras. Luego cada letra de la nota gasta una copia de esa tabla, y la primera letra cuyo conteo ya es cero demuestra que la nota no se puede formar. Cada letra de ambos strings se toca una vez, así que el tiempo es O(n + m), y la tabla tiene como máximo 26 entradas, así que el espacio extra es O(1).
from collections import Counter
def can_spell(note, banner):
stock = Counter(banner) # letter -> copies left
for ch in note:
if stock[ch] == 0:
return False # this letter has run out
stock[ch] -= 1
return True
print(can_spell("aab", "baa")) # -> True
print(can_spell("aa", "ab")) # -> False
print(can_spell("", "xyz")) # -> True¿Lo que te frena es la idea y no el código? Conteo de frecuencias lo explica.