Log inSign up
easyleetcodeNot Started

Find the Difference

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1 · Example:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: e is the letter that was added.

Example 2 · Example:

Input: s = "", t = "y"
Output: "y"
Explanation: y is the letter that was added.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply bitwise XOR to isolate single odd-frequency elements.
  • Utilize ASCII sum arithmetic for difference detection.
  • Compare trade-offs between counting arrays and mathematical shortcuts.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • When one array/string is an exact permutation of another plus one single inserted element.
  • Finding the unique odd-frequency element among duplicates.

Algorithmic Decision Tree:

  • Bit Manipulation (XOR Duplicates Cancellation)
  • ASCII Sum Difference

Connected Patterns:

Single NumberMissing NumberSet Mismatch

1. Sorting and Linear Scanning

Intuition

Sort s and t. Iterate through both sorted strings: the first index where s[i] != t[i] indicates t[i] is the extra character. If the loop completes without a mismatch, the extra character is the last element t[t.length - 1].

When to apply: Basic exploratory approach.

Algorithm

  1. Sort string s and string t.
  2. Loop i from 0 to s.length - 1:
  3. If s[i] != t[i], return t[i].
  4. If no mismatch within loop, return t[t.length - 1].

Sorting Both Strings & Linear Mismatch Search

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, d, e]
Current operationSTEP 1 OF 6
Observation: Sort both strings alphabetically
Visual state
Values and pointers at this exact step
array
S
a
b
c
d
e
0
1
2
3
4
Variables at this step
Pointer i
0
Pointer j
0
Matched
'a'
Mismatch Found
false
Check / comparison
s[0] ('a') == t[0] ('a'). Characters match.
Decision / next transition
Index 0 matched. Advance both pointers to index 1.
Why this step matters

Observation: Sort both strings alphabetically. Compare s[0]='a' and t[0]='a'.

Decision: Elements match. Advance i and j.

Invariant: Prefix of length 1 matches identically.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 char findTheDifference(std::string s, std::string t) {
8 std::sort(s.begin(), s.end());
9 std::sort(t.begin(), t.end());
10 for (int i = 0; i < (int)s.size(); ++i) {
11 if (s[i] != t[i]) return t[i];
12 }
13 return t.back();
14 }
15};
16
17int main() {
18 Solution sol;
19 std::cout << sol.findTheDifference("abcd", "abcde") << std::endl; // __SF_TOKEN_A__
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting strings of length N takes O(N log N) time.
  • Space complexity: O(N) for sorted copies

Why Brute Force Doesn't Scale:

Bitwise XOR eliminates the need for data structures or sorting entirely.

Only a single primitive accumulator variable is needed.

2. Frequency Counting Array

Intuition

Initialize an integer frequency array of size 26 with zeros. Increment counts for each character in s. Then iterate through t, decrementing counts. If any character's count becomes negative, it must be the newly added character.

When to apply: When maintaining intuitive frequency count logic without bitwise tricks.

Algorithm

  1. Initialize int count[26] = {0}.
  2. For each char c in s: count[c - 'a']++.
  3. For each char c in t:
  4. Decrement count[c - 'a'].
  5. If count[c - 'a'] < 0, return c.
  6. Return empty character (fallback).

Frequency Counting Array Increment & Decrement

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, d, e]
Current operationSTEP 1 OF 6
Observation: Initialize 26-slot frequency array
Visual state
Values and pointers at this exact step
array
S
a:1
b:1
c:1
d:1
0
↑ COUNTS S
1
2
3
Variables at this step
Populated
s="abcd"
Array Size
26
Total Tallied
4
Check / comparison
Populate frequency array of size 26 using string s.
Decision / next transition
Counts after scanning s: a:1, b:1, c:1, d:1.
Why this step matters

Observation: Initialize 26-slot frequency array. Increment counts for all chars in s = "abcd".

Decision: count['a']=1, count['b']=1, count['c']=1, count['d']=1.

Invariant: All characters in s registered.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 char findTheDifference(std::string s, std::string t) {
8 int count[26] = {0};
9 for (char c : s) count[c - 'a']++;
10 for (char c : t) {
11 if (--count[c - 'a'] < 0) {
12 return c;
13 }
14 }
15 return ' ';
16 }
17};
18
19int main() {
20 Solution sol;
21 std::cout << sol.findTheDifference("abcd", "abcde") << std::endl; // __SF_TOKEN_A__
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N) — Two linear passes over strings of length N and N + 1 with constant space.
  • Space complexity: O(1) (26-element array)

3. Bitwise XOR / Sum Difference

Intuition

Initialize char xorVal = 0. Iterate through string s and XOR each character into xorVal. Then iterate through string t and XOR each character into xorVal. Since XOR is commutative and associative, all identical characters cancel out c ^ c = 0, leaving only the extra character.

When to apply: The optimal, most elegant single-variable technique in O(N) time and O(1) space.

Algorithm

  1. Initialize char result = 0.
  2. For each character in s: result ^= s[i].
  3. For each character in t: result ^= t[i].
  4. Return result.

ASCII Difference / Bitwise XOR Single-Pass Detection

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, b, c, d, e]
Current operationSTEP 1 OF 6
Observation: Initialize XOR accumulator: xorSum = 0
Visual state
Values and pointers at this exact step
array
S
a
b
c
d
e
0
↑ i=0: 'a'
1
2
3
4
Variables at this step
Index
0
s[0]
a
t[0]
a
Current XOR
0
Check / comparison
XOR s[0] ('a'=97) ^ t[0] ('a'=97) = 0.
Decision / next transition
Identical characters cancel out to 0.
Why this step matters

Observation: Initialize XOR accumulator: xorSum = 0. At i = 0, both strings have 'a'.

Decision: xorSum ^= 'a' ^ 'a' = 0. Identical characters cancel out completely.

Invariant: Since x \oplus x = 0, every duplicated character will vanish.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 char findTheDifference(std::string s, std::string t) {
7 char res = 0;
8 for (char c : s) res ^= c;
9 for (char c : t) res ^= c;
10 return res;
11 }
12};
13
14int main() {
15 Solution sol;
16 std::cout << sol.findTheDifference("abcd", "abcde") << std::endl; // __SF_TOKEN_A__
17 std::cout << sol.findTheDifference("", "y") << std::endl; // __SF_TOKEN_A__
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(N) — Traverses both strings once in O(N + (N+1)) = O(N) operations using 1 integer register.
  • Space complexity: O(1) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Sorting ComparisonO(N log N)O(N)Straightforward and visual.Unnecessary sorting overhead.
2.Frequency Counting ArrayO(N)O(1) (26-element array)Very easy to reason about and modify.Requires two passes and 26-element storage.
3.Bitwise XOR / ASCII Sum DifferenceOptimalO(N)O(1) strictlySingle variable, single pass, zero extra array allocations, optimal constant factor.Requires knowing bitwise or arithmetic trick.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Assuming the added character must appear at the end of t (it can be anywhere).

Pitfall 2:

Allocating expensive hash tables or sort operations when XOR is O(1) space.

Crucial Edge Cases to Validate:

  • s is empty string (s = '', t = y): Loop over s is skipped, t has 1 char, result is 0 ^ y = y.
  • Extra character is a duplicate of an existing character in s (e.g. s = a, t = aa): Frequency and XOR count handle odd parity correctly: a ^ a ^ a = a.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Immediately point out the XOR property (or ASCII sum difference) to impress the interviewer with optimal O(1) space knowledge.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does XORing all characters in s and t yield the unique extra character?

Back to DSA Sheet