Pular para o conteúdo

Bilhete de resgate com letras de revista

Fácil#frequency-count#hash-map~10 min

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

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

Travou na ideia, e não no código? Contagem de frequência explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado