Blogs Hub

Find the Difference - Hash Table - Easy - LeetCode - MiniTV

Find the Difference - Hash Table - Easy - LeetCode - मिनी टीवी

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)