# 389. Find the Difference

## Approach 1: Bit

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: char findTheDifference(string s, string t) { char ans = 0; for (const char c : s) ans ^= c; for (const char c : t) ans ^= c; return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public char findTheDifference(String s, String t) { char ans = 0; for (final char c : s.toCharArray()) ans ^= c; for (final char c : t.toCharArray()) ans ^= c; return ans; } } 
 1 2 3 4 5 6 7 8 class Solution: def findTheDifference(self, s: str, t: str) -> str: count = collections.Counter(s) for i, c in enumerate(t): count[c] -= 1 if count[c] == -1: return c 

## Approach 2: Hash Table

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public: char findTheDifference(string s, string t) { vector count(128); for (const char c : s) ++count[c]; for (const char c : t) if (--count[c] < 0) return c; throw; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public char findTheDifference(String s, String t) { int[] count = new int[128]; for (final char c : s.toCharArray()) ++count[c]; for (final char c : t.toCharArray()) if (--count[c] < 0) return c; throw new IllegalArgumentException(); } }