Valid Anagram

Условие

Даны 2 строки: s и t. Вернуть true, если s является анограммой t, и false в противном случае.

Анаграмма — это слово или фраза , образованные путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Примеры

Input: s = "anagram", t = "nagaram"

Output: true

Input: s = "rat", t = "car"

Output: false

Решение

fun isAnagram(s: String, t: String): Boolean {
    // Если у строк разная длина - это 100% не анаграммы.
    if (s.length != t.length) return false
    
    // Создаем массив из 26 элементов (количество англ букв) для подсчета частоты символов
    val charCount = IntArray(26) // [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    
		// Итерируемся по всем символам строки s и увеличиваем значение элемента (char - 'a') для каждого символа
		// Для "rat" массив станет таким: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0], позиции букв a, r, t станут 1.
    s.forEach { char ->
        charCount[char - 'a']++
    }

    // Итерируемся по всем символам строки t и скручиваем счетчики
    // Для "cat" массив станет таким: [0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], скрутили a и t, r осталась 1, c стала -1.
    t.forEach { char ->
        charCount[char - 'a']--
    }

    // Проверяем, если все значения в массиве равны нулю - строки являются анаграммами
    return charCount.all { it == 0 }
}

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

O(n), где n — длина строки. Мы проходим строки только по одному разу.

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

O(1), так как используемый массив фиксированного размера (26 элементов).