DAY 70 - Find the Difference
Tags: leetcode, coding, algorithms, beginners
Published: 2023-08-12 19:22:56

Hey Guys! Today we are on the 70th day and we are going to  solve another bit manipulation problem.

---


## Question: [Find the Difference](https://leetcode.com/problems/find-the-difference)

## Problem Description

_You are given two strings `s` and `t`._

_String `t` is generated by random shuffling string `s` and then add one more letter at a random position._

_Return the letter that was added to `t`._

---

### _Example 1:_

> **Input:** s = "abcd", t = "abcde"
> **Output:** "e"
> **Explanation:** 'e' is the letter that was added.


---



### Hashing Approach:

The hashing approach which first comes to our mind deals with creating a character frequency hash to track the occurrences of characters in both strings. By iterating through both strings and updating the hash with the frequency of characters, we can compare the frequency of characters in both strings to find the added character.

Alternatively we could also have used a hashmap for characters but since both these approaches are relatively same , I am not going to approach it.

### Code:

```cpp
char findTheDifference(string s, string t) {
        char ans;
        int hash[26] = {0};

        for(auto it : s){
            hash[it -'a']++;
        }

        for(auto itr : t){
            hash[itr - 'a']--;
        }
        for(auto it : hash){
            cout << it << " ";
        }
        for(int i = 0; i < 26; i++){
            if(hash[i] == -1){
                ans = i + 'a';
            }
        }
        return ans;
    }
```

---

## Approach using Sum Calculation

This approach utilizes the difference between the ASCII values of corresponding characters in `s` and `t`. By calculating this difference and adding it to the subsequent characters in `t`, the added character's ASCII value will be present in the last position.

### Code:

```cpp

class Solution {
public:
    char findTheDifference(string s, string t) 
    {
      for(int i=0;i<s.size();i++)
		t[i+1]+=t[i]-s[i]; //Passing the diff: (t[i]-s[i]) to t[i+1]
      return t[t.size()-1]; //The diff will be carried over to the last element eventually
    }
};

```

---

## XOR-based Approach

The XOR-based approach uses the property of the XOR operation where when we XOR a value with itself results in 0. By XORing the ASCII values of corresponding characters in both strings, only the ASCII value of the different character remains.


### Code:

```cpp
char findTheDifference(string s, string t) {
        char res = t[s.size()];
        for(int i = 0; i < s.length(); i++){
            res^=s[i] ^ t[i];
        }
        return res;
    }

```

---

## Sorting Approach/Brute Force

In this approach, both strings are sorted, and then we iterate through them to find the differing character. The differing character corresponds to the added character.

### Code:

```cpp
int n = s.length();
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        for(int i=0; i<n; i++) if(s[i]!=t[i]) return t[i];
        return t[n];
    }
```

---


## Complexity Analysis:

| Approach                   | Time Complexity | Space Complexity                              
|---------------------------|-----------------|------------------|--------------------------------------------|
| Hashing                   | O(n)            | O(n)             |             
| ASCII Sum Calculation     | O(n)            | O(1)             |                     
| XOR-based                 | O(n)            | O(1)             |  
| Sorting                   | O(n log n)      | O(1)             |          


---


Thanks for reading!. Feedback is highly appreciated!