Find the Difference
Easy · Arrays & Hashing · Hash Table · String · Bit Manipulation · Sorting
Problem
You are given two strings s and t. String t was made by shuffling s and then inserting one more letter at some position.
Return the letter that was added to t. It may be a copy of a letter that already occurs in s.
Examples
Input: s = "code", t = "ecdoe" Output: "e"
t has two e's while s has only one.
Input: s = "", t = "q" Output: "q"
s is empty, so the only letter of t is the added one.
Input: s = "xyz", t = "zwxy" Output: "w"
w does not occur in s.
Constraints
- 0 <= len(s) <= 1000
- len(t) == len(s) + 1
- s and t consist of lowercase English letters
Approaches
- Baseline: sort both strings — time O(n log n), space O(n)
Follow-up
XOR finds one odd-one-out among pairs. With two added letters it leaves only their XOR, which many pairs share, so you need counts again (or the trick of splitting on a set bit, which works for two distinct values). If the strings are streamed and too large to store, both XOR and the sum need only one running number.
Related problems
Start free on Cariara · Coding problems · System design studio
