🔗 Problem Link

LeetCode 389 – Find the Difference

👉 https://leetcode.com/problems/find-the-difference/

Introduction

This is a very clever problem.

At first glance, you might think:

1. Use a HashMap
2. Count frequencies
3. Compare both strings

But there’s a much smarter and cleaner way to solve it using character arithmetic (ASCII values).

This problem teaches an important lesson:

Sometimes math can replace extra space.

Let’s break it down.

📌 Problem Understanding

You are given two strings:

1. s
2. t

String t is created by:

1. Shuffling string s
2. Adding one extra character at a random position

Your task:

Return the extra character added to t.

Example 1

Example 2

🧠 First Intuition (Brute Force Thinking)

When solving this for the first time, a common approach would be:

1. Count frequency of characters in s
2. Count frequency of characters in t
3. Compare both
4. The one with extra count is the answer

That works in O(n) time and O(26) space.

But we can do better.

🚀 Smarter Approach – ASCII Sum Trick

💡 Key Insight

Characters are stored as integer ASCII values.

If:

1. We add all ASCII values of characters in t
2. Subtract all ASCII values of characters in s

What remains?

👉 The ASCII value of the extra character.

Because:

All matching characters cancel out.

Only the added character remains.

💻 Your Code

🔍 Step-by-Step Explanation

1️⃣ Initialize Total

This will store the running ASCII difference.

2️⃣ Add All Characters of t

We add ASCII values of every character in t.

3️⃣ Subtract All Characters of s

We subtract ASCII values of every character in s.

4️⃣ Return Remaining Character

After subtraction, only the extra character’s ASCII value remains.

We convert it back to char.

🎯 Why This Works

Let’s take example:

ASCII Sum:

Subtract:

Everything cancels except the extra letter.

Simple and powerful.

⏱ Complexity Analysis

Time Complexity: O(n)

1. One loop over t
2. One loop over s

Space Complexity: O(1)

No extra data structure used.

🔥 Even Smarter Approach – XOR Trick

Another elegant method is using XOR:

Why XOR Works?

Properties:

1. a ^ a = 0
2. a ^ 0 = a
3. XOR is commutative

If we XOR all characters in both strings:

Matching characters cancel out.

Only the extra character remains.

XOR Version

This is considered the most elegant solution.

🏁 Final Thoughts

This problem teaches:

1. Thinking beyond brute force
2. Using mathematical properties
3. Understanding ASCII representation
4. Using XOR smartly

Sometimes the best solution is not about data structures —

it’s about recognizing hidden math patterns.