Find the Difference - Solution & Explanation
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:
Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter that was added.
Example 2:
Input: s = "", t = "y" Output: "y"
Constraints:
0 <= s.length <= 1000t.length == s.length + 1sandtconsist of lowercase English letters.
Approach Overview
Problem Overview: You are given two strings s and t. String t is created by shuffling s and adding one extra character. Your task is to return that additional character. The challenge is identifying the extra element efficiently without expensive comparisons.
Approach 1: Frequency Count Approach (O(n) time, O(1) space)
This approach counts how many times each character appears in both strings. Use a fixed-size frequency array or a hash map from the hash table pattern. First iterate through s and increment counts. Then iterate through t and decrement counts. The moment a count becomes negative, that character is the extra one. This works because every character from s cancels out except the additional one in t. The method is straightforward and easy to implement across languages.
Approach 2: XOR Approach (O(n) time, O(1) space)
XOR exploits the property that a ^ a = 0 and a ^ 0 = a. XOR every character from both strings together. Characters that appear in both strings cancel out, leaving only the extra character. Iterate through s and t, XOR their ASCII values into a single variable, then convert the result back to a character. This technique uses constant space and avoids any auxiliary data structures. It is a classic bit manipulation trick often expected in interviews.
Approach 3: Sorting and Comparing (O(n log n) time, O(1) extra space)
Sort both strings and scan them from left to right. The first position where characters differ reveals the extra character in t. If all characters match during the scan, the extra character is the final element in the sorted t. Sorting simplifies the comparison logic but increases time complexity due to the sorting step. This approach mainly demonstrates understanding of ordering techniques from sorting.
Recommended for interviews: The XOR approach is typically preferred. It runs in linear time, constant space, and demonstrates familiarity with bit manipulation tricks. The frequency count method is also acceptable and often easier to reason about during discussion. Sorting works but is rarely considered optimal.
Approach 1: Frequency Count Approach
This approach involves creating frequency counts for both strings. Loop through each character in both strings, updating a counter for each character. By comparing these counters, you can determine which character has a different count, revealing the additional character in string t.
This solution initializes an array of size 26 (for each letter in the English alphabet) to zero. It then iterates over string s, incrementing the count for each letter. It subsequently iterates over string t, decrementing the count. The first character that results in a non-positive count is the additional character.
Complexity
The time complexity is O(n) where n is the length of s as we iterate over t once in the worst case. Space complexity is O(1) because the storage requirement is constant (the fixed size count array).
Approach 2: XOR Approach
This approach leverages the properties of the XOR bitwise operator. XOR'ing the same numbers results in 0 and XOR is commutative and associative, meaning the order of operations doesn't matter. By XOR'ing all characters in both strings, one additional character will be left out, since all others cancel each other out.
The C solution iterates over each character in both s and t, applying the XOR operation between them. Given XOR's properties, each pair of identical characters across s and t will cancel each other out, leaving the extra character as the result.
Complexity
Time complexity is O(n) as both strings are traversed. Space complexity is O(1) because only a single variable is used.
Approach 3: Counting
We can use a hash table or array cnt to count the occurrence of each character in string s, then traverse string t. For each character, we subtract its occurrence in cnt. If the corresponding count is negative, it means that the occurrence of this character in t is greater than in s, so this character is the added character.
The time complexity is O(n), and the space complexity is O(|\Sigma|), where n is the length of the string, and \Sigma represents the character set. Here the character set is all lowercase letters, so |\Sigma|=26.
Approach 4: Summation
We can sum the ASCII values of each character in string t, then subtract the sum of the ASCII values of each character in string s. The final result is the ASCII value of the added character.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Frequency Count Approach | The time complexity is O(n) where n is the length of |
| XOR Approach | Time complexity is O(n) as both strings are traversed. Space complexity is O(1) because only a single variable is used. |
| Counting | — |
| Summation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count (Hash Map / Array) | O(n) | O(1) | General solution when using hash tables or counting characters |
| XOR Bit Manipulation | O(n) | O(1) | Best choice when constant space and elegant bit trick is preferred |
| Sorting and Compare | O(n log n) | O(1) | Simple conceptual approach when sorting is acceptable |
Video Solution
Find the Difference - Leetcode 389 - Python • NeetCodeIO • 14,466 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Difference easy or hard?
Find the Difference Python/Java solution
How to solve Find the Difference in O(n)?
What is the best approach for Find the Difference?
Is Find the Difference asked at Google/Amazon/Meta?
What data structure is used in Find the Difference?
What is the time complexity of Find the Difference?
Ready to solve this problem?
Practice Find the Difference with our built-in code editor and test cases.
Practice on FleetCode