LESSON 275 OF 441 · HASH TABLE

Find the Difference in C#: O(n) with a Dictionary

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 Dictionary from each letter to how many times it appears in s. Then walk through t: each letter uses up one copy from the Dictionary. 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 Dictionary is O(1) on average: O(n) time.
The Dictionary never holds more than 26 letters, so the extra space is O(1).

STEP 1 OF 8

Guided

Ctrl + Enter to check

Find The Difference in C#, explained

Problem overview

The method FindTheDifference receives two strings of lowercase letters. t is s shuffled with one extra letter added somewhere. The method returns the added letter as a char, in O(n) time.

For s = "abcd" and t = "abcde" the answer is 'e'. For s = "" and t = "y" it is 'y'.

Approach: count `s` once, then spend the counts

The brute-force solution counts a letter in s and in t again for every letter of t, which costs O(n²). The waste is that the counts of s never change. Count them once and keep them.

A Dictionary<char, int> maps each letter to the number of copies of it that s holds. Then walk through t and treat each letter as using up one copy. Since t is s plus one letter, every letter of t finds a copy waiting, except one: the letter whose copies in s have all been used already, or that s never had. That letter is the extra one.

Take s = "aab" and t = "abab". The dictionary starts as a: 2, b: 1. Reading t, the 'a' leaves a: 1, the 'b' leaves b: 0, the next 'a' leaves a: 0, and the last letter is 'b', whose count is already 0. The method returns 'b'. Note that it returns the letter at the point where its copies run out, which may be a different position from where the extra letter was inserted. Since equal letters are interchangeable, the answer is the same.

Step by step

Create the dictionary as Dictionary<char, int> counter. Keys are letters and values are how many copies of each letter are still unused.
Loop over s with foreach (char c in s) to fill it.
Add one to the letter's count. counter.GetValueOrDefault(c, 0) gives the stored count, or 0 when the letter isn't in the dictionary yet. Adding 1 and assigning back through counter[c] = ... creates the entry on first sight and updates it later.
Loop over t with another foreach (char c in t).
Look for a letter with no copies left. If counter.GetValueOrDefault(c, 0) == 0, the letter either never appeared in s or all its copies are used up.
Return that letter. It is the extra one.
Otherwise spend a copy by subtracting 1 from the letter's count. This line is reached only when the count was at least 1.
Return a placeholder after the loop. C# needs a return on every path, and the constraints make the loop always return first, so ' ' is never actually returned for valid input.

The solution in C#

class Solution {
    public char FindTheDifference(string s, string t) {
        Dictionary<char, int> counter = new Dictionary<char, int>();
        foreach (char c in s) {
            counter[c] = counter.GetValueOrDefault(c, 0) + 1;
        }
        foreach (char c in t) {
            if (counter.GetValueOrDefault(c, 0) == 0) {
                return c;
            }
            counter[c] = counter.GetValueOrDefault(c, 0) - 1;
        }
        return ' ';
    }
}

The C# details worth knowing:

Reading a missing key throws. counter['a'] on a dictionary without that key throws KeyNotFoundException. Writing with counter['a'] = 5 is different: it adds the key if it is missing and overwrites it otherwise. That asymmetry is why the code reads with GetValueOrDefault.
GetValueOrDefault(c, 0) returns the stored value, or the second argument when the key is absent. It does not add the key to the dictionary. Without the second argument it would return default(int), which is also 0. Other ways to write the same step are TryGetValue and ContainsKey.
The namespace. Dictionary lives in System.Collections.Generic, so a standalone file needs using System.Collections.Generic; at the top.
The same name twice. Both loops declare char c. That is allowed because each variable's scope is only its own loop.
A char is a fine key. Characters compare by value and hash quickly. An int[26] indexed by c - 'a' would also work here, since the input is lowercase letters only; the dictionary doesn't depend on that assumption.

Complexity

Time: O(n). The first loop runs once per letter of s, and the second runs at most once per letter of t. Each dictionary read or write takes constant time on average, so the whole method is linear in the length of t.

Space: O(1). The dictionary holds one entry per distinct letter. The input has only 26 lowercase letters, so it never has more than 26 entries, no matter how long the strings are.

Edge cases and common mistakes

Empty s. The dictionary stays empty, and the first letter of t has count 0, so it is returned. s = "", t = "y" gives 'y'.
The extra letter repeats a letter of s. s = "zz" and t = "zzz" returns 'z', on the third 'z', when both copies are used up. Checking only whether the key exists would miss this.
Indexing the dictionary directly. Writing counter[c] + 1 instead of GetValueOrDefault throws KeyNotFoundException the first time a letter is seen.
Subtracting before checking. If the count is decreased first, a letter with no copies left would go to -1 and the check would never see 0 for it.
Counting both strings. It works, but costs a second pass and more code. Spending the counts of s while reading t does the comparison in the same loop.

Testing

s = "abcd", t = "abcde" gives 'e'.
s = "", t = "y" gives 'y'.
s = "aab", t = "abab" gives 'b'.
s = "zz", t = "zzz" gives 'z'.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free