How do you solve Find the Difference?

Use a hash map to count the frequency of each character in t. Then iterate over s, decrementing the count for each character. Finally, iterate over the hash map to find the character with count 1, which is the extra letter added in t.

What pattern does Find the Difference use?

The Pattern: Hash Maps (Frequency Counting) The Heuristic: When comparing two collections where one has exactly one extra element, counting frequencies with a hash map and comparing counts efficiently reveals the difference in O(n) time.

Find the Difference | Hash Maps

Q: What is the time complexity of Find the Difference?

O(n). The solution iterates through both strings once each, performing O(1) average-time hash map operations per character, resulting in linear time complexity.

Problem

Given two strings s and t where t is generated by shuffling s and adding one more letter at a random position, return the letter that was added in t.

0 ≤ s.length ≤ 10⁴
t.length == s.length + 1
s and t consist of lowercase English letters.

Example

Input: s = "abcd", t = "abcde"

Output: "e"

The brute-force approach would be to compare every character in s with every character in t, which is inefficient. Instead, the algorithm counts the frequency of each character in t, then subtracts the frequency of each character in s. The character with a frequency difference of 1 is the extra letter added. For example, counting characters in t yields {'a':1, 'b':1, 'c':1, 'd':1, 'e':1}. Subtracting counts from s removes the counts for 'a', 'b', 'c', and 'd', leaving 'e' with count 1, which is returned.

Approach

Straightforward Solution

A naive approach would compare each character in s against t, resulting in O(n^2) time complexity, which is inefficient for large strings.

Core Observation

The extra letter in t is the one whose frequency count exceeds that in s by exactly one. Counting characters and comparing frequencies reveals this difference directly.

Path to Optimal

Preview

Recognizing that frequency counts can be used to identify the extra character leads to a linear time solution. By counting characters in t and decrementing counts using s, the leftover character with count 1 is the added letter…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a hash map to count the frequency of each character in t. Then iterate over s, decrementing the count for each character…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The solution iterates through both strings once each, performing O(1) average-time hash map operations per character, resulting in linear time complexity.

Space

O(1)

The hash map stores counts for lowercase English letters only, which is a fixed size of at most 26 entries, resulting in constant auxiliary space.

Solution

Python

1class Solution:
2    def findTheDifference(self, s: str, t: str) -> str:
3        counts = {}
4
5        for char in t:
6            counts[char] = counts.get(char, 0) + 1
7
8        for char in s:
9            counts[char] -= 1
10
11        for char, count in counts.items():
12            if count == 1:
13                return char
14
15        return ""

Step-by-Step Solution

1

Build Frequency Map for String t

3counts = {}
5for char in t:
6    counts[char] = counts.get(char, 0) + 1

Objective

To count the occurrences of each character in string t using a hash map.

Key Insight

Counting characters in t first captures the full frequency profile including the extra letter. Using a hash map allows O(1) average-time updates and lookups, enabling efficient frequency tracking.

Interview Quick-Check

Core Logic

The hash map stores character counts from t, which forms the baseline frequency profile including the extra letter.

Common Pitfalls & Bugs

Forgetting to initialize counts properly or using a data structure with slower lookups can degrade performance.

2

Subtract Frequency Counts Using String s

To decrement the frequency counts for each character found in s, effectively removing characters that are common to both strings.

3

Identify and Return the Extra Letter

To find the character in the frequency map with a count of 1 and return it as the extra letter.

4

Return Empty String if No Extra Letter Found (Fallback)

To provide a fallback return value in case no extra letter is found, ensuring function completeness.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

counts[char] -= 1

Decrement the count for the current character in the hash map.

This line is the core operation that isolates the extra letter by removing all characters present in s, ensuring only the added character remains with a positive count.

Line 12 Critical

if count == 1:

Check if the count for the character is exactly 1.

This conditional check is the decisive moment that confirms the identity of the extra letter, enabling immediate return.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why does counting character frequencies and comparing them reveal the extra letter efficiently?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find the Difference from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find the Difference drill

or drill a free problem

1	`class Solution:`
2	`def findTheDifference(self, s: str, t: str) -> str:`
3	`counts = {}`
4
5	`for char in t:`
6	`counts[char] = counts.get(char, 0) + 1`
7
8	`for char in s:`
9	`counts[char] -= 1`
10
11	`for char, count in counts.items():`
12	`if count == 1:`
13	`return char`
14
15	`return ""`