Ransom Note

🇷🇺 Название: Записка с требованием выкупа
LeetCode: ransom-note
Временная сложность: O(n+m)
Пространственная сложность: O(1)

Решение

from collections import Counter  


class Solution:  
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:  
        r_count = Counter(ransomNote)  
        m_count = Counter(magazine)  

        for char in r_count:  
            if r_count[char] > m_count.get(char, 0):  
                return False  
        return True

🇺🇸 Условие

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

🇷🇺 Условие

Примеры

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

{
  "examples": [
    {
      "input": {
        "ransomNote": "a",
        "magazine": "b"
      },
      "output": false
    },
    {
      "input": {
        "ransomNote": "aa",
        "magazine": "ab"
      },
      "output": false
    },
    {
      "input": {
        "ransomNote": "aa",
        "magazine": "aab"
      },
      "output": true
    }
  ]
}

Ограничения

• \(1 \leq ransomNote.length, magazine.length \leq 10^5\)
• ransomNote and magazine consist of lowercase English letters.

Потребление ресурсов

⏱ Time complexity: O(n+m)

• Counter(ransomNote) — O(n), где n = len(ransomNote)
• Counter(magazine) — O(m), где m = len(magazine)
• Проход по r_count — максимум O(k), где k — число уникальных символов в ransomNote (в худшем случае k = 26 для латиницы)

Итог: O(n + m)

🧠 Space complexity: O(1)

• Counter использует память пропорционально количеству уникальных символов.
• Для латиницы максимум 26 символов → считается O(1)
• Если допускать Unicode/большой алфавит → O(k)

Итог: O(1) при фиксированном алфавите, иначе O(k)

easy hash-table string counting

---

Metadata

• title_rus: Записка с требованием выкупа
• difficulty: Easy
• leetcode_url: https://leetcode.com/problems/ransom-note/
• topics: ['Hash Table', 'String', 'Counting']
• time: O(n+m)
• space: O(1)
• grind75: True
• tags: ['Counting', 'Easy', 'Hash Table', 'String', 'problem']
• git_revision_date_localized: 5 июля 2025 г.
• git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_revision_date_localized_tag:
• git_revision_date_localized_raw_date: 5 июля 2025 г.
• git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_revision_date_localized_raw_iso_date: 2025-07-05
• git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_revision_date_localized_raw_timeago:
• git_revision_date_localized_raw_custom: 05. июля 2025
• git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_site_revision_date_localized_tag:
• git_site_revision_date_localized: 5 июля 2025 г.
• git_site_revision_date_localized_raw_date: 5 июля 2025 г.
• git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_site_revision_date_localized_raw_iso_date: 2025-07-05
• git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_site_revision_date_localized_raw_timeago:
• git_site_revision_date_localized_raw_custom: 05. июля 2025