Problem overview
The method findTheDifference(String s, String t) gets two strings of lowercase letters. The string t is s shuffled with one extra letter added at a random position, and the method returns that letter as a char. The length of s is from 0 to 1000, and t is one longer.
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 s once, then use the counts up while reading t
The brute-force solution counts each letter of t inside s again and again, which is O(n²). The waste is that the answer for a letter never changes, so count the letters of s once and keep the results in a HashMap from letter to count.
Then treat the map as a supply of letters. Read t one letter at a time. For each letter, take one copy from the supply. Since t contains all the letters of s plus one more, the supply runs out exactly once: at the extra letter. The first letter of t that finds no copy left, because its count is 0 or because it was never in the map, is the answer.
Take s = "aa" and t = "aaa". The map starts as {a=2}. The first 'a' of t uses a copy (count 1), the second uses another (count 0), and the third finds the count at 0, so 'a' is returned. The letter was in s, but it occurs once more in t, and the count shows it.
With s = "abcd" and t = "abcde", the map is {a=1, b=1, c=1, d=1}. Reading t, the letters a, b, c and d each use their single copy and bring their counts to 0. Then e arrives: it is not in the map, so it reads as 0 and is returned. The work is two passes, one per string, instead of one pass per letter.
Step by step
- Create the map
counter, typedMap<Character, Integer>and backed by aHashMap. It will hold how many copies of each letter ofsare still available. - Loop over the letters of
swiths.toCharArray(). - Increment each letter's count with
counter.merge(c, 1, Integer::sum).mergestores 1 when the key is new, and otherwise combines the old value and 1 withInteger::sum. It replaces the usual "get, add one, put back" code. - Loop over the letters of
t. - Check the supply with
counter.getOrDefault(c, 0) == 0. A letter that is not in the map reads as 0, and so does a letter whose copies are used up. Both mean there is nothing left to match this letter with. - Return the letter when the supply is empty. It is the extra one.
- Use up a copy otherwise, with
counter.merge(c, -1, Integer::sum). - Add a final return of
' 'after the loop. Java needs a return on every path, and with valid input the loop returns first.
The solution in Java
class Solution {
public char findTheDifference(String s, String t) {
Map<Character, Integer> counter = new HashMap<>();
for (char c : s.toCharArray()) {
counter.merge(c, 1, Integer::sum);
}
for (char c : t.toCharArray()) {
if (counter.getOrDefault(c, 0) == 0) {
return c;
}
counter.merge(c, -1, Integer::sum);
}
return ' ';
}
}
The code uses Map and HashMap from java.util, so a standalone file needs import java.util.*;.
The Java details worth a look:
- Boxing. A
Mapcan't hold primitives, so the key type isCharacterand the value type isInteger. Thecharandintvalues are boxed and unboxed automatically. getreturnsnullfor a missing key. Writingcounter.get(c) == 0would throw aNullPointerExceptionfor a letter that is not in the map, because Java unboxes thenullto compare it.getOrDefault(c, 0)avoids that.Integer::sumis a method reference to the static methodInteger.sum(int, int).mergecalls it with the old value and the new one.- Counts can sit at 0. The code never removes an entry. Merging
-1leaves a key with value 0, and the check treats 0 the same as missing.
Complexity
Time: O(n). One pass over s and one over t, with a constant number of map operations per letter. Each merge and getOrDefault is O(1) on average.
Space: O(1). The strings hold lowercase letters only, so the map never has more than 26 entries.
Edge cases and common mistakes
- An empty
s. The map stays empty, and the only letter oftreads as 0, so it is returned at once.("", "y")gives'y'. - A repeated extra letter.
("aa", "aaa")gives'a'. Testing only whether the letter is in the map, instead of its count, would miss it. - Calling
geton a missing key. A plaincounter.get(c) == 0throws for letters not ins, and the extra letter is often one of those. UsegetOrDefault. - Checking after decrementing. If you merge
-1first and test afterwards, a negative count appears for the extra letter and a check for exactly 0 would miss it. Test first, then decrement. - Building the map from
tand walkings. The idea can be flipped, but then the extra letter is the one left over in the map, which needs a final scan of the map. The version here exits early.
Testing
"abcd","abcde"gives'e'."","y"gives'y'."aa","aaa"gives'a'.
