DAY 70 - Find the Difference

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

Question: 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:

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:

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:

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:

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:

Thanks for reading!. Feedback is highly appreciated!