Start learning free

LESSON 276 OF 442 · HASH TABLE

Find the Difference in Kotlin: O(n) with a HashMap of Counts

Practice O(n) Read the full explanation

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.

 

Example 1:

Input: s = "abcd", t = "abcde"
Output: e
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: y

 

Constraints:

  • 0 <= s.length <= 1000
  • t.length == s.length + 1
  • s and t consist of lowercase English letters.
Note:

For this lesson, your algorithm should run in O(n) time, where n is the length of t.



The brute force counts each letter of t in s again and again. Count the letters of s only once, and keep the counts.

Store the counts in a HashMap from each letter to how many times it appears in s. Then walk through t: each letter uses up one copy from the HashMap. The first letter of t that has no copy left (its count is 0, or it was never there) is the extra one.

We walk through s once and t once, and each lookup in the HashMap is O(1) on average: O(n) time.
The HashMap never holds more than 26 letters, so the extra space is O(1).
STEP 1 OF 8
    Ctrl + Enter to check

    KOTLIN · HASH TABLE

    Find The Difference in Kotlin, explained

    Problem overview

    findTheDifference(s, t) receives two strings of lowercase letters. The string t is s shuffled, with one extra letter added at a random position, so t is always exactly one character longer. The function returns the added letter as a Char.

    For s = "abcd" and t = "abcde" it returns 'e'. For s = "" and t = "y" it returns 'y'. This lesson asks for O(n) time, where n is the length of t.

    Approach: count once, then use the counts up

    The brute-force answer counts the letters of both strings again for every character of t, which costs O(n²). The waste is that the counts of s never change, yet they get recomputed over and over.

    The fix is to count s a single time and keep the result in a HashMap from each letter to the number of times it occurs. Then walk through t and treat the map as a stock of copies: each letter of t takes one copy from the stock. Since t is s plus one letter, every letter finds a copy except the extra one. The first letter that arrives to find its stock at zero, or missing from the map entirely, is the answer.

    Here is s = "aab" and t = "baab". Counting s gives a two copies and b one. Now walk through t:

    1. b has 1 copy, so take it. b is at 0.
    2. a has 2 copies, so take one. a is at 1.
    3. a has 1 copy, so take it. a is at 0.
    4. b has 0 copies left, so it is the extra letter, and the function returns 'b'.

    Notice that the letter returned is a letter s already had. The map handles that case correctly because it tracks how many copies remain, not just whether a letter was seen.

    This trades a little memory for a lot of time. The map costs space, but it turns each lookup from a pass over a string into a single step, so the two loops add up to 2n steps instead of up to 2n². A later lesson on this problem removes even the map.

    Step by step

    1. Create the map. HashMap<Char, Int> named counter links each letter to how many times it occurs in s. It is a val because the variable never points at a different map, even though the map's contents change.
    2. Loop over s. This pass builds the counts.
    3. Add one per letter. counter.getOrDefault(c, 0) returns the current count, or 0 for a letter not yet in the map. Adding 1 and storing the result covers both the first sighting and every later one.
    4. Loop over t. This second pass uses the counts up.
    5. Check the stock. If counter.getOrDefault(c, 0) == 0, the letter is either missing or already used up.
    6. Return it. That letter has no partner in s, so it is the added one.
    7. Otherwise take a copy. Subtract 1 from its count. This line is only reached when the count was at least 1.
    8. Add a fallback return after the second loop. For valid input it never runs, but Kotlin needs a Char on every path.

    The solution in Kotlin

    class Solution {
    fun findTheDifference(s: String, t: String): Char {
        val counter = HashMap<Char, Int>()
        for (c in s) {
            counter[c] = counter.getOrDefault(c, 0) + 1
        }
        for (c in t) {
            if (counter.getOrDefault(c, 0) == 0) {
                return c
            }
            counter[c] = counter.getOrDefault(c, 0) - 1
        }
        return ' '
    }
}

    Kotlin details worth a look:

    • counter[c] = ... is shorthand for counter.put(c, ...). Reading with the same brackets, counter[c], gives an Int?: for a missing key it is null, not 0. That is why the solution uses getOrDefault(c, 0), which always gives a plain Int. Writing counter[c] ?: 0 would do the same job.
    • HashMap in Kotlin is the same class as Java's java.util.HashMap, so Java methods such as getOrDefault are available on the JVM.
    • Looping over a String yields Char values, matching the map's key type.
    • Return type. The method returns Char, so the fallback is the character ' ', written with single quotes.

    Complexity

    Time: O(n). The first loop runs over s and the second over t, so there are about 2n steps in total. Each map read or write takes constant time on average.

    Space: O(1). The input uses only lowercase letters, so the map never holds more than 26 entries, no matter how long the strings are. If the alphabet were unbounded, the space would grow with it.

    Edge cases and common mistakes

    • Empty s. The map stays empty, and the first letter of t has no copy, so it is returned at once.
    • The extra letter duplicates an existing one. Only a count catches this. A set of seen letters would accept the second b in the example above.
    • Checking before subtracting. The zero test must come first. If you subtract first, the count can go negative and the extra letter is missed.
    • Using counter[c] in arithmetic. counter[c] + 1 doesn't compile for a map of Int, because the result of the lookup is nullable.
    • Dropping the fallback return. The compiler rejects a function whose loop might finish without returning.

    Testing

    • s = "abcd", t = "abcde" gives 'e'.
    • s = "", t = "y" gives 'y'.
    • s = "aab", t = "baab" gives 'b'.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free