# 389-find-the-difference

## Question

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

Given two strings s and t which consist of only lowercase letters.

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

Find the letter that was added in t.

Example:

``````Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.
``````

## Thought Process

1. Hash Table
1. Use count array to store the frequency of character, increase for string s and decrease t
2. Loop from letter a to z, the first encounter of count = 1 is our answer
3. Time complexity O(n)
4. Space complexity O(n) or O(1)
2. Sum
1. Similar to above, we add the character from s and deduct the character from t
2. The final sum is the character
3. Time complexity O(n)
4. Space complexity O(1)
3. XOR
1. XOR all the character
2. Time complexity O(n)
3. Space complexity O(1)

## Solution

``````class Solution {
public char findTheDifference(String s, String t) {
int[] count = new int;
int n = s.length();
for (int i = 0; i < n; i++) {
count[s.charAt(i) - 'a']--;
count[t.charAt(i) - 'a']++;
}
count[t.charAt(n) - 'a']++;
int c = 0;
for (int i = 0; i < 26; i++) {
if (count[i] == 1) {
c = i + 'a';
break;
}
}
return (char) c;
}
}
``````
``````class Solution {
public char findTheDifference(String s, String t) {
int diff = 0;
for (int i = 0; i < s.length(); i++) {
diff -= s.charAt(i);
diff += t.charAt(i);
}
diff += t.charAt(s.length());
return (char) diff;
}
}
``````
``````class Solution {
public char findTheDifference(String s, String t) {
int n = s.length();
char c = t.charAt(n);
for (int i = 0; i < n; i++) {
c ^= s.charAt(i);
c ^= t.charAt(i);
}
return c;
}
}
``````