# 389. Find the Difference

## use HashMap



T:  O(n)

S:  O(26)

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



## use bit

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FJfGKdUizKDuOATgzbHsk%2Fimage.png?alt=media\&token=ee980cd6-327c-4150-bc60-197f6e9e1ff2)

T: O(n)

S: O(1)

```java
class Solution {
    public char findTheDifference(String s, String t) {
        
        if (s.length() == 0) {
            return t.charAt(0);
        }
        
        char res = '\0';
        
        for (int i = 0; i < s.length(); i++) {
            res ^= s.charAt(i);
            res ^= t.charAt(i);
        }
        res ^= t.charAt(t.length()-1);

        return res;
    }
}
```
