You get two strings, s and t. To make t, someone shuffled s and added one extra letter.
Return the extra letter as a character.
Example 1:
Input: s = "plan", t = "nlapk" Output: k Explanation: t is "plan" shuffled, plus a 'k'.
Example 2:
Input: s = "moon", t = "noomo" Output: o Explanation: s has two o's. t has three o's. The extra letter is an 'o'.
Example 3:
Input: s = "", t = "w" Output: w
Constraints:
shas 0 to 1,000 letters.thas exactly one more letter thans.- Both strings use only lowercase English letters.
For this lesson, your algorithm should run in O(n) time, where n is the length of t.
The brute force counts each letter of
t in s again and again. Count the letters of s only once, and keep the counts.
Store the counts in a dict from each letter to how many times it appears in
s. Then walk through t: each letter uses up one copy from the dict. The first letter of t that has no copy left (its count is 0, or it was never there) is the extra one.
We walk through
s once and t once, and each lookup in the dict is O(1) on average: O(n) time.The dict never holds more than 26 letters, so the extra space is O(1).
Free plan: 30 tutor messages. PRO is unlimited.
Saved
Ctrl + Enter to check
