Find The Difference

You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.

Source

package questions

import _utils.UseCommentAsDocumentation
import kotlin.test.assertEquals

/**
 * You are given two strings s and t.
 * String t is generated by random shuffling string s and then add one more letter at a random position.
 * Return the letter that was added to t.
 *
 * [Source](https://leetcode.com/problems/find-the-difference/)
 */
@UseCommentAsDocumentation
private fun findTheDifference(s: String, t: String): Char {
    val record = mutableMapOf<Char, Int>()
    for (i in s) {
        record[i] = (record[i] ?: 0) + 1
    }
    for (i in t) {
        if (!record.containsKey(i)) {
            // Found the newly added letter
            return i
        }
        record[i] = record[i]!! - 1
        if (record[i] == 0) {
            // remove if count == 0
            record.remove(i)
        }
    }
    // The matching letters were removed from the map so the key that remains is the answer
    return record.keys.first()
}

fun main() {
    assertEquals('e', findTheDifference(s = "abcd", t = "abcde"))
    assertEquals('y', findTheDifference(s = "", t = "y"))
    assertEquals('a', findTheDifference(s = "a", t = "aa"))
}

---

View on GitHub

Updated on 2021-10-13