---
description: "Author: @wingkwong, @radojicic23 | https://leetcode.com/problems/find-the-difference/"
tags: [Hash Table, String, Bit Manipulation, Sorting]
---

# 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)](../0100-0199/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.

<Tabs>
<TabItem value="cpp" label="C++">
<SolutionAuthor name="@wingkwong"/>

```cpp
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;
    }
};
```

</TabItem>

<TabItem value="kotlin" label="Kotlin">
<SolutionAuthor name="@wingkwong"/>

```kt
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()
    }
}
```

</TabItem>
</Tabs>

## 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.

<Tabs>
<TabItem value="cpp" label="C++">
<SolutionAuthor name="@wingkwong"/>

```cpp
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';
    }
};
```

</TabItem>
</Tabs>

## 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.

<Tabs>
<TabItem value="cpp" label="C++">
<SolutionAuthor name="@wingkwong"/>

```cpp
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();
    }
};
```

</TabItem>

<TabItem value="py" label="Python">
<SolutionAuthor name="@radojicic23"/>

```py
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]
```

</TabItem>

<TabItem value="js" label="JavaScript">
<SolutionAuthor name="@radojicic23"/>

```js
/**
 * @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];
};
```

</TabItem>
</Tabs>
