Leet389: Find The Difference.

Intro

You very likely missed the intro article A.K.A disclaimer, to this series but here goes. This is the first actual article with real content (for this series) and, we are tackling an easy leetcode problem, I attempted the champagne glass that was the "problem of the day" prior. Let's just say it didn't go as planned 😄. #chucklingEmoji.

While today's problem might have real-world applications, I don't know what they are yet so, we'll focus on understanding and solving it for now. Grab your favorite bodysuit and let's dive in.

Problem Statement

You are given two strings s and t.

String t is generated by randomly shuffling string s and then adding one more letter at a random position.

Return the letter that was added to t.

Initial Thought

Clearly, this is a problem where you have to iterate through a string and try to decipher if you have seen that string before. we all know, at least I know, that the general approach to that, that will lead to a linear time complexity is to introduce a hash map data structure. (Because well, fast lookup).
That part is obvious. where you might start to go wrong is using a test case of short strings. that way, it won't be obvious that you only have 26 alphabets in the English language and you might need to track the frequency of appearance,
my initial approach was to use the hash map and map a key of the alphabet to true showing that I had seen it before.
what happens when an alphabet shows up the 2nd, or 3rd..... time? Now you can see how that approach is wrong right?

Actual Approach

Givens:
1. we need to use an hash map to keep track of the letters.
2. We need to also record the frequency of seeing it. How many times Have I seen this letter?
you might start to wake up now, if we were given a string s that has 10 letters, and t with 11 letters, clearly if we store both in separate maps and compare, whatever key in the map that has 1 more than the same key in the other map is the answer.

Arrgh, I didn't want to have to illustrate this but...

s= "abcdefde" t= "cdeabdzef" //you can see that we added z right?
//now, the map looks something like this
sMap ={a:1,b:1,c:1,d:2,e:2,}
tMap={a:1,b:1,c:1,d:2,e:2, z:1}

looking at the map, the answer is obvious right ?Z. but getting the answer programmatically might be a bit tricky. so, instead of using 2 separate maps, why not 1 right? and as we have populated the tMap using the string t, we can depopulate it in the same vain as the s string until everything defaults back to 0, and z becomes 1. Now, we can loop through the object and look for the key that has a value of 1. There goes our answer. we can do it the other way round too.

Implementation

function findTheDifference(s: string, t: string): string {
    const map = {};
    for(const char of t){
        map[char] = (map[char]?? 0)+1
    }
    for(const char of s){
        // I expect to always have at least 1 map[char]
        map[char] = map[char] -1;
    }
    for(const key in map){
        if(map[key] ===1)return key
    }
};

Perhaps, we should solve this in go too. flexing my beginner go-lang skills. (I don't like yet that there is strings and there is byte in Go. can't we just stick with strings only? I'll get to understand the benefits later though). at least, I definitely love that for loops and while loops have the same syntax.

func findTheDifference(s string, t string) byte {
   myMap := make(map[rune]int) 
//here, we used a type of rune instead of string or byte.
// why? that is a task for the reader

   for _,char := range t{
    //unlike JS, we can do this in go because it will default the value 
    //to zero since it knows it is to be an integer. 
    //we don't have to manually default it ourselves. 
      myMap[char] = myMap[char]+ 1
   }

   for _,char := range s{
       myMap[char] =  myMap[char] -1
   }

   for key, val := range myMap{
       if val == 1{
           return byte(key)
       }
   }

   return 'a'
}

Complexity Analysis

in our approach, the maximum size of our map is 26. since we are only dealing with 26 English alphabets. that is constant space.
for time, we iterate through the s and t strings once each and once through the map, that is 0(n+m) + 0(1). simplified to 0(n).
Time complexity: linear
space complexity: Constant

Lesson Learned

Well, I learned why you use a rune type instead of string or byte for situations like when I initialized myMap in the go solution. myMap := make(map[rune]int)
It is the reader's responsibility to find out why

Other Approaches

There is the Ascii method where you convert the letters to Ascii numbers and add them all up. s is added separately, and so is t. then, subtracted from each other. the difference gives a corresponding English alphabet. however, I do not like this approach, it is certainly faster because working with numbers is faster for computers, but imagine a scenario where 2 letters were added, you can see the ASCII method might become useless or more difficult to implement. exactly. stick with the mapping method.

Real World Applications.

I think it is very similar to ceaser cipher which is a very old method of encryption.
That is all I know

Conclusion