Coding Interview PatternsFind the Difference
EasyBitwise Manipulation
Find the Difference
Explanation & Solution
Description
You are given two strings s and t.
String t is generated by random shuffling string s and then adding one more letter at a random position.
Return the letter that was added to t.
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.
Constraints
0 <= s.length <= 1000t.length == s.length + 1sandtconsist of lowercase English letters.
Approach
Bitwise Manipulation pattern
Key Insight
- This is essentially the Single Number problem applied to characters
- XOR approach handles all cases and avoids potential overflow in some languages
- Time: O(n) | Space: O(1)
Visualization
Input:
[a, b, c, d, e], s = abcd
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps