# Find the Difference
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-difference)
Canonical: https://scaleengineer.com/dsa/problems/find-the-difference
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
---
## Problem
\[Fetch error\]

# Approaches
## Brute Force using Sorting
This approach relies on sorting. If we sort the characters of both strings, they will be identical up to the length of the original string `s`. By comparing the sorted strings character by character, the first mismatch we find will reveal the extra letter added to `t`. If all characters match up to the end of `s`, the extra character must be the very last character of the sorted `t`.
**Time:** O(N log N), where N is the length of the string `t`. The dominant operation is sorting the character arrays. · **Space:** O(N), where N is the length of the string `t`. This space is required to store the character arrays for sorting. Some sorting algorithms might use additional space (e.g., `O(log N)` for quicksort's recursion stack).
**Pros:** The logic is straightforward and easy to understand.
**Cons:** The time complexity of `O(N log N)` is suboptimal for this problem.; It requires extra space to hold the character arrays, which can be `O(N)`.
### Explanation
The core idea is that after sorting, two identical sets of characters would result in identical arrays. Since `t` has one extra character, its sorted version will be identical to `s`'s sorted version until the point where the extra character is positioned, or the extra character will be appended at the end.

```java
import java.util.Arrays;

class Solution {
    public char findTheDifference(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        Arrays.sort(sChars);
        Arrays.sort(tChars);

        for (int i = 0; i < sChars.length; i++) {
            if (sChars[i] != tChars[i]) {
                return tChars[i];
            }
        }

        // If the loop finishes, the extra character is the last one in t
        return tChars[tChars.length - 1];
    }
}
```
### Algorithm
- Convert both strings `s` and `t` into character arrays, let's call them `sChars` and `tChars`.
- Sort both `sChars` and `tChars` alphabetically.
- Iterate from the first character up to the length of `s`.
- In each iteration, compare `sChars[i]` with `tChars[i]`.
- If the characters at the current index `i` are different, `tChars[i]` is the added character, so return it.
- If the loop completes without finding any difference, it means the extra character is the last character in `tChars`. Return `tChars[t.length() - 1]`.

## Frequency Counting using Hash Map
This method involves counting the frequency of each character. We can use a hash map (or a simple array if the character set is fixed, like 26 lowercase letters) to store the character counts of the original string `s`. Then, we iterate through the modified string `t`. When we encounter a character that is not in our frequency map or whose count is already zero, we have found the added letter.
**Time:** O(N), where N is the length of string `t`. We iterate through both strings once, and hash map operations take, on average, O(1) time. · **Space:** O(K), where K is the number of unique characters in the string. If the character set is fixed (e.g., ASCII or 26 lowercase letters), this can be considered O(1).
**Pros:** Achieves linear time complexity, which is a significant improvement over sorting.; It's a versatile approach that works for any character set.
**Cons:** Has some overhead associated with hash map operations (calculating hash codes, handling potential collisions).; Uses more space than the most optimal solutions, especially if the character set is large.
### Explanation
By first counting all characters in `s`, we establish a baseline. Then, as we iterate through `t`, we effectively 'remove' each character we see from our baseline counts. The character in `t` that cannot be removed (because it wasn't in `s` at all, or we've already seen all instances of it from `s`) is our answer.

For a character set limited to lowercase English letters, an array of size 26 can be used instead of a hash map for slightly better performance.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public char findTheDifference(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();

        // Populate map with character counts from s
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        // Decrement counts for characters in t
        for (char c : t.toCharArray()) {
            int count = map.getOrDefault(c, 0);
            if (count == 0) {
                // This character is the extra one
                return c;
            } else {
                map.put(c, count - 1);
            }
        }

        // This line should not be reachable given the problem constraints
        return ' ';
    }
}
```
### Algorithm
- Create a hash map to store character frequencies.
- Iterate through the original string `s` and for each character, increment its count in the hash map.
- Iterate through the modified string `t`. For each character in `t`:
  - Check if the character is in the map and its count is greater than 0. 
  - If it is, decrement the count.
  - If the character is not in the map or its count is already 0, this must be the added character. Return it.

## Sum of Character Codes
This is a clever mathematical approach. Since `t` is composed of all characters from `s` plus one extra character, the sum of the character codes (like ASCII values) of `t` will be exactly the sum of character codes of `s` plus the code of the added character. By finding the difference between the two sums, we can identify the added character.
**Time:** O(N), where N is the length of string `t`. We need to iterate through both strings once. · **Space:** O(1), as we only need a few variables to store the sums, regardless of the input size.
**Pros:** Very efficient with O(N) time complexity and O(1) space complexity.; Extremely simple and concise to implement.
**Cons:** There is a theoretical, though highly unlikely, risk of integer overflow if the strings are extremely long and use characters with large Unicode values.
### Explanation
We can find the result in a single pass. We can start with the character code of the last character in `t` (since `t` is one character longer than `s`) and then iterate from 0 to `s.length() - 1`, adding the character code from `t` and subtracting the one from `s` in each step. This avoids two separate loops.

```java
class Solution {
    public char findTheDifference(String s, String t) {
        int sumS = 0;
        int sumT = 0;

        for (char c : s.toCharArray()) {
            sumS += c;
        }

        for (char c : t.toCharArray()) {
            sumT += c;
        }

        return (char)(sumT - sumS);
    }
}
```
### Algorithm
- Initialize an integer variable, `charSum`, to 0.
- Iterate through the characters of string `t` and add the ASCII (or Unicode) value of each character to `charSum`.
- Iterate through the characters of string `s` and subtract the ASCII (or Unicode) value of each character from `charSum`.
- The final value of `charSum` will be the ASCII value of the added character.
- Cast this integer value back to a `char` and return it.

## Optimal Solution using Bit Manipulation (XOR)
This is a highly elegant and efficient solution that uses the properties of the bitwise XOR operator. The XOR operation has the property that `x ^ x = 0` and `x ^ 0 = x`. If we XOR all characters from both strings together, every character that is common to both `s` and `t` will appear twice in the operation, effectively canceling itself out (e.g., `c ^ c = 0`). The only character that doesn't get canceled is the one that was added to `t`.
**Time:** O(N), where N is the length of string `t`, as we iterate through both strings once. · **Space:** O(1), as it only requires a single variable to store the accumulated XOR value.
**Pros:** Achieves optimal O(N) time and O(1) space complexity.; Avoids the potential integer overflow issue of the summation method.; It's a common and powerful technique for problems involving finding a unique element in a set.
**Cons:** The concept of bitwise XOR might be less intuitive for beginners compared to direct counting or summation.
### Explanation
The beauty of this approach is that the order of operations doesn't matter due to the commutative and associative properties of XOR. We can combine the two loops into one for a more compact implementation. The result is a robust, single-pass solution with minimal space usage.

Example: `s = "ab"`, `t = "bac"`
`result = ('a' ^ 'b') ^ ('b' ^ 'a' ^ 'c')`
`result = ('a' ^ 'a') ^ ('b' ^ 'b') ^ 'c'`
`result = 0 ^ 0 ^ 'c'`
`result = 'c'`

```java
class Solution {
    public char findTheDifference(String s, String t) {
        char result = 0;

        for (char c : s.toCharArray()) {
            result ^= c;
        }

        for (char c : t.toCharArray()) {
            result ^= c;
        }

        return result;
    }
}
```
### Algorithm
- Initialize a character or integer variable, `result`, to 0.
- Iterate through each character of string `s` and perform a bitwise XOR operation between the character and `result`.
- Iterate through each character of string `t` and perform a bitwise XOR operation between the character and `result`.
- The final value of `result` will be the added character.

# Solutions
### Java

```java
class Solution { public char findTheDifference ( String s , String t ) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < s . length (); ++ i ) { ++ cnt [ s . charAt ( i ) - 'a' ]; } for ( int i = 0 ;; ++ i ) { if (-- cnt [ t . charAt ( i ) - 'a' ] < 0 ) { return t . charAt ( i ); } } } }
```

### Python

```python
class Solution:
    def findTheDifference(self, s: str, t: str) -> str: cnt = Counter(s) for c in t: cnt[c] -= 1 if cnt[c] < 0: return c

```

### CPP

```cpp
class Solution { public: char findTheDifference ( string s , string t ) { int cnt [ 26 ]{}; for ( char & c : s ) { ++ cnt [ c - 'a' ]; } for ( char & c : t ) { if ( -- cnt [ c - 'a' ] < 0 ) { return c ; } } return ' ' ; } };
```