Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input: s = "abcd" t = "abcde"
Output: e
Explanation: 'e' is the letter that was added.
public class Solution {
public char FindTheDifference(string s, string t) {
var map = new Dictionary<char, int>();
for(int i=0;i<s.Length;i++){
if(map.ContainsKey(s[i])){
map[s[i]]++;
}
else{
map.Add(s[i],1);
}
}
var map2 = new Dictionary<char, int>();
for(int i=0;i<t.Length;i++){
if(map2.ContainsKey(t[i])){
map2[t[i]]++;
}
else{
map2.Add(t[i],1);
}
}
foreach(var item in map2){
if(!map.ContainsKey(item.Key)){
return item.Key;
}
if(map[item.Key]!=item.Value){
return item.Key;
}
}
return '0';
}
}Time Complexity: O(n)
Space Complexity: O(n)
