Ransom Note

Условие

Даны две строки ransomNote и magazine. Нужно определить, можно ли составить строку ransomNote из символов строки magazine. Каждый символ строки magazine можно использовать не более одного раза.

Примеры

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

Output: false

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

Output: false

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

Output: true

Решение

fun canConstruct(ransomNote: String, magazine: String): Boolean {
    val charCount = IntArray(26)  // Массив для подсчета количества каждой буквы в magazine

    // Подсчитываем количество каждой буквы в magazine
    for (char in magazine) {
        charCount[char - 'a']++
    }

    // Проверяем, можно ли составить ransomNote из magazine
    for (char in ransomNote) {
        if (charCount[char - 'a'] == 0) {
            return false  // Если буквы недостаточно, вернуть false
        }
        charCount[char - 'a']--  // Уменьшаем количество использованной буквы
    }

    return true  // Если все буквы найдены, вернуть true
}

Временная сложность

O(n + m), где n — длина magazine, а m — длина ransomNote, так как мы проходим по каждой строке один раз.

Пространственная сложность

O(1), так как используется фиксированный массив размера 26 для хранения количества букв.