0389 - Find the Difference (Easy)

Problem Link

https://leetcode.com/problems/find-the-difference/

Problem Statement

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.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

Approach 1: Bit Manipulation

Same idea as 0136 - Single Number (Easy).

Prerequisite: You should understand properties of XOR.

Let's have a quick review.

• If we take XOR of a number and a zero, the result will be that number, i.e. $a \oplus 0 = a$.
• If we take XOR of two same numbers, it will return 0, i.e. $a \oplus a = 0$.
• If we take XOR of multiple numbers, the order doesn't affect the result, i.e. $a \oplus b \oplus c = a \oplus c \oplus b$.

Therefore, we apply XOR on each character. The same characters will cancel out each other. What's left is the answer.

C++

Written by @wingkwong

class Solution {
public:
    char findTheDifference(string s, string t) {
        char ans = 0;
        // take XOR for each character: ans = ans ^ x
        for (auto x : s) ans ^= x;
        for (auto x : t) ans ^= x;
        return ans;
    }
};

Kotlin

Written by @wingkwong

class Solution {
    fun findTheDifference(s: String, t: String): Char {
        var ans = 0
        for (x in s + t) ans = ans xor x.toInt()
        return ans.toChar()
    }
}

Approach 2: Counting

We can store the occurrence for each character. As t has one more character, we can count t first, iterate s to subtract the occurrences. The answer will be the one which has one occurrence.

C++

Written by @wingkwong

class Solution {
public:
    char findTheDifference(string s, string t) {
        int occ[26] = {0};
        // count the occurrence for t
        for (auto x : t) occ[x - 'a']++;
        // instead of using an extra array,
        // we decrease the occurrence in `occ`
        for (auto x : s) occ[x - 'a']--;
        for (int i = 0; i < 26; i++) {
            // the answer will be the one with occurrence = 1
            if (occ[i] == 1) {
                return i + 'a';
            }
        }
        // returning any character would work as it never reaches here
        return 'a';
    }
};

Approach 3: Sorting

We can sort both input and compare each character one by one. If there is a difference, then return $t[i]$. Otherwise, return the last character of $t$ as the first $len(s)$ characters are same.

C++

Written by @wingkwong

class Solution {
public:
    char findTheDifference(string s, string t) {
        // sort s in ascending order
        sort(s.begin(), s.end());
        // sort t in ascending order
        sort(t.begin(), t.end());
        for (int i = 0; i < s.size(); i++) {
            // s = "abcde"
            // t = "abcdde"
            // "e" is not same as "d" at position 4 (0-base)
            // hence, return t[i], i.e. "d"
            if (s[i] != t[i]) {
                return t[i];
            }
        }
        // for the case like
        // s = "abcd"
        // t = "abcde"
        return t.back();
    }
};

Python

Written by @radojicic23

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s = "".join(sorted(list(s)))
        t = "".join(sorted(list(t)))
        for i in range(len(s)):
            if s[i] != t[i]:
                return t[i]
        return t[-1]

JavaScript

Written by @radojicic23

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function (s, t) {
  const sortedS = s.split("").sort().join("");
  const sortedT = t.split("").sort().join("");
  for (let i = 0; i < s.length; i++) {
    if (sortedS[i] != sortedT[i]) {
      return sortedT[i];
    }
  }
  return sortedT[sortedT.length - 1];
};