324. Find the Difference
You are given two strings s and t, both consisting of lowercase English letters. t was produced by shuffling the letters of s and then inserting one extra letter at some position.
Return that extra letter — the single character of t that is not accounted for by the letters of s.
Be careful: the extra letter may be a duplicate of a letter s already contains, so what matters is letter counts, not mere membership.
Example 1:
Input: s = "listen", t = "silentg"
Output: "g"
Explanation: "silent" is a shuffle of "listen"; the leftover letter is "g".
Example 2:
Input: s = "", t = "y"
Output: "y"
Explanation: s is empty, so the only letter of t is the extra one.
Constraints:
- 0 ≤ s.length ≤ 1000
- t.length == s.length + 1
- s and t consist of lowercase English letters.
- t is a shuffle of s with exactly one extra letter inserted.
Hints:
Tally the 26 letter counts of s, then walk t subtracting one per letter — the letter whose tally dips below zero is the intruder.
For O(1) extra space with no counting array at all: XOR the character codes of every letter in both strings. Identical pairs cancel (x ⊕ x = 0), leaving exactly the extra letter's code.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "listen", t = "silentg"
Expected output: "g"