122. The Extra Letter
A messenger wrote the lower case letters of the string s on cards, shuffled them and then, by mistake, added one extra card carrying a lower case letter. The string t lists the cards after the mix-up, in the shuffled order.
Return the letter that was added. It is the only letter whose count in t is higher than its count in s; it may be equal to a letter that already occurs in s. A solution that uses one pass and constant memory is expected.
Example 1
- Input:
- s = "xyz", t = "zxwy"
- Output:
- "w"
- Explanation:
The cards of t contain x, y and z once each, plus a w that is not in s.
Example 2
- Input:
- s = "aab", t = "abaa"
- Output:
- "a"
- Explanation:
s has two a letters, while t has three, so the added letter is a.
Constraints
1 ≤ s.length ≤ 105
t.length == s.length + 1
s and t contain only lower case letters, and t is a shuffle of s plus exactly one extra letter
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)