How do you approach Find the Difference?

A frequency count of s versus t works: one letter's count in t will be one higher.

What is the time complexity of Find the Difference?

Time complexity: O(n) - one pass over each string. Space complexity: O(1) - a single integer accumulator.

What are common mistakes on Find the Difference?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

Sitelet https://gitgood.dev/coding/find-the-difference

gitGood.dev

← Back to problems

Find the Difference

EasyAlgorithms

Description

You are given two strings s and t.

String t is generated by randomly shuffling string s and then adding 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"

Example 3

Input: s = "a", t = "aa"

Output: "a"

Explanation: A second copy of an existing letter counts as the added letter.

Constraints

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

Find the Difference: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 6 test cases (3 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

A frequency count of s versus t works: one letter's count in t will be one higher.
Can you do it with O(1) extra space? Think about what XOR does to pairs of equal values.
XOR all character codes of both strings together - every matched pair cancels, leaving only the added letter.

The optimal approach

Show the approach: XOR All Character Codes

XOR has two key properties: `x ^ x = 0` and it's order-independent. Every letter from `s` has a matching copy in `t` and cancels out, so XOR-ing all character codes of both strings leaves exactly the code of the added letter.

A frequency-count hash map also works in O(n) time but uses O(1)-to-O(26) extra space; the XOR trick is the classic interview follow-up.

Time: O(n) - one pass over each string
Space: O(1) - a single integer accumulator

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.