Watch 10 video solutions for Find the Difference, a easy level problem involving Hash Table, String, Bit Manipulation. This walkthrough by Kevin Naughton Jr. has 19,863 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 + 1s and t consist of lowercase English letters.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 | 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 |