**Explanation**

There are many ways to do this question that involve sorting or using a dictionary, but I will show you the optimal solution that runs strictly in O(n) with O(1) space.

The idea to this solution is to take advantage of ASCII codes. First, we sum up the ASCII codes of all characters in *t*. Then, we subtract the ASCII codes of all characters in *s* from *t*'s sum. The remaining value is the ASCII code for the newly added character.

**Time Complexity**

The time complexity to my solution is O(n) where n is the number of characters in input *t*, since scanning through *t* runs in O(n) and *s* runs in O(n-1): O(n) + O(n-1) = O(n).

```
class Solution {
public char findTheDifference(String s, String t) {
int sum = 0;
for (int i = 0; i < t.length(); i++) {
sum += (int) t.charAt(i);
}
for (int i = 0; i < s.length(); i++) {
sum -= (int) s.charAt(i);
}
return (char) sum;
}
}
```