Find the Difference

Условие

Даны две строки s и t, состоящие из строчных букв. Строка t формируется путем случайного перемешивания строки s с добавлением одного дополнительного символа. Нужно найти этот дополнительный символ.

Примеры

Input: s = “abcd”, t = “abcde”

Output: “e”

Explanation: Символ ‘e’ добавлен в строку t.

Input: s = “”, t = “y”

Output: “y”

Решение

fun findTheDifference(s: String, t: String): Char {
    var result = 0

    // XOR всех символов в s
    for (char in s) {
        result = result xor char.toInt()
    }

    // XOR всех символов в t
    for (char in t) {
        result = result xor char.toInt()
    }

    return result.toChar()  // Преобразуем результат обратно в символ
}

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

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

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

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