Bilhete de resgate com letras de revista
A missão
Problema
Um fabricante de letreiros recorta letras de uma faixa que sobrou para formar uma nova mensagem. Dadas duas strings em minúsculas, note e banner, retorne True se note puder ser escrita com letras de banner, em que cada letra de banner pode ser usada no máximo uma vez. As duas strings têm até 100.000 letras, então evite procurar de novo na faixa para cada letra do bilhete.
Exemplos
Input: note = "aab", banner = "baa"
Output: True
Por quê: a faixa tem dois a e um b, exatamente o que o bilhete precisa
Input: note = "aa", banner = "ab"
Output: False
Por quê: o bilhete precisa de dois a, e a faixa só tem um
Input: note = "", banner = "xyz"
Output: True
Por quê: edge case: um bilhete vazio não precisa de letra nenhuma
Dicas
0 / 3
A ordem não importa aqui, só quantas letras de cada tipo você tem. Que única tabela resumiria a faixa?
Conte cada letra da faixa uma vez. Depois, cada letra do bilhete é uma retirada dessa contagem.
Percorra o bilhete e subtraia um da contagem da letra. Se uma contagem fosse ficar abaixo de zero, a faixa ficou sem aquela letra, então retorne False.
- Tempo-alvo
- O(n + m)
- Espaço-alvo
- O(1)
Restrições
- note and banner are lowercase letters
- each string has at most 10⁵ letters
Solução
Só importa o número de cópias de cada letra, então a faixa é reduzida a uma tabela de contagens de letras em uma única passada. Cada letra do bilhete então gasta uma cópia dessa tabela, e a primeira letra cuja contagem já é zero prova que o bilhete não pode ser montado. Cada letra das duas strings é tocada uma vez, então o tempo é O(n + m), e a tabela guarda no máximo 26 entradas, então o espaço extra é 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")) # -> TrueTravou na ideia, e não no código? Contagem de frequência explica isso.