Problem overview
String t is a shuffled copy of s with one extra lowercase letter added. The method findTheDifference returns that letter. With s = "abcd" and t = "abcde" the result is "e", and with s = "" and t = "y" it is "y".
This version must run in O(n) time, where n is the length of t.
Approach: count s once, then spend the counts
The brute-force solution counts a letter of t inside s from scratch every time, which costs a full walk per letter and O(n²) overall. The waste is clear: s never changes, so its letter counts only need to be computed once.
Build an object that maps each letter to how many times it appears in s. Then walk through t and treat each count as a supply of copies. Each letter of t uses up one copy. Every letter of s has a partner in t, so every use finds a copy waiting, except for the extra letter. When a letter of t finds no copy left, either because its count has reached 0 or because it never appeared in s, that letter is the extra one.
Take s = "ae" and t = "aea". Counting s gives { a: 1, e: 1 }. In t, the first "a" uses its copy and the count becomes 0. "e" does the same. The second "a" finds a count of 0, so the answer is "a". The letter was in s already, and the counts still expose it.
Step by step
- Create
counteras an empty object typed as a map from strings to numbers. The annotation{ [key: string]: number }says that any string key holds a number. - Loop over the letters of
swithfor...of, naming the letterc. - Increase that letter's count. A letter seen for the first time has no entry, and reading it gives
undefined. The expression(counter[c] || 0)turns that into 0 before adding 1. - Loop over the letters of
tin a second loop. - Test
!counter[c]. A missing entry (undefined) and a count of 0 are both falsy, so one test covers both ways of running out. - Return
cinside that branch. This is the extra letter. - Decrement
counter[c]after the test. Only a letter that still has a copy reaches this line, so the count never goes below 0.
The solution in TypeScript
class Solution {
findTheDifference(s: string, t: string): string {
const counter: { [key: string]: number } = {};
for (const c of s) {
counter[c] = (counter[c] || 0) + 1;
}
for (const c of t) {
if (!counter[c]) {
return c;
}
counter[c]--;
}
}
}
The TypeScript details worth a closer look:
- The index signature is only a type.
{ [key: string]: number }tells the compiler what to expect, socounter["z"]is typed asnumber. It is erased when the code compiles to JavaScript. At run time the object is a plain object, and reading a letter that was never stored givesundefined, not 0. That is the reason for|| 0. constdoes not freeze the object.const counterprevents reassigning the variable, and the properties can still change.- Truthiness.
!counter[c]is true forundefinedand for0. That works because a stored count is never negative. The same shortcut would be wrong if 0 were a legitimate stored value you wanted to tell apart from "missing". - Plain objects are safe here. The keys are single lowercase letters, which can't clash with built-in property names such as
constructor. For arbitrary string keys, aMap<string, number>is the safer choice, read withmap.get(c) ?? 0. - The missing final
return. The guarantee thatthas one extra letter means the second loop always returns. The lesson's compiler settings don't flag the end of the method. An input without an extra letter would giveundefinedat run time, whatever the declared return type says.
Complexity
Time: O(n). The first loop runs once per letter of s and the second once per letter of t, which is one more than s. Each object read and write takes constant time on average, so the total is linear in n.
Space: O(1). counter holds at most 26 keys, one per lowercase letter, however long the strings are. The size of the alphabet is a constant, so the space doesn't grow with n.
Edge cases and common mistakes
- Empty
s. The first loop does nothing andcounterstays empty. The only letter oftfinds no entry, so it is returned. - The extra letter duplicates a letter of
s.s = "a"witht = "aa"returns"a", because the second"a"finds a count of 0. A check that asked only whether the letter exists inswould fail here. - Decrementing before the test. A count of 0 would become -1, which is truthy, so the test would no longer see that the letter had run out. Test first, decrement second.
- Forgetting the default. Writing
counter[c] = counter[c] + 1on a new letter givesundefined + 1, which isNaN.NaNis falsy, so the second loop would report that letter as the extra one. - Returning the wrong end. The answer is the letter of
tthat runs out, so the second loop must walkt, nots.
Testing
s = "abcd",t = "abcde"gives"e".s = "",t = "y"gives"y".s = "aab",t = "baaa"gives"a".s = "ae",t = "aea"gives"a".
