Find the Difference — Solution in Python, Java & C++
Find the Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find the Difference is an easy coding problem on strings, hash table and sorting, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Sorting, Bit Manipulation
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
String t is generated by shuffling string s and then inserting one extra letter at a random position.
Return that added letter.
Example 1
Input: s = "abcd", t = "abcde"
Output: e
Example 2
Input: s = "", t = "y"
Output: y
Example 3
Input: s = "a", t = "aa"
Output: a
Constraints
0 <= s.length <= 39t.length == s.length + 1Both consist of lowercase English letters.
Hints for Find the Difference
Hint 1
Counting letters in both strings and finding the surplus works and is easy to read.
Hint 2
Slicker: XOR the character codes of every letter in both strings.
Hint 3
Each shared letter cancels itself out, leaving only the inserted one.
How to solve Find the Difference
XOR the character codes of both strings; every shared letter cancels, leaving the inserted one.
Approach
- XOR all codes of
sandtinto one accumulator. - Return the character with that code.
Why it works
Each letter of s appears in t as well, so it is XORed twice and vanishes; only the extra letter is XORed once.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Summing codes and subtracting also works; counting letters is the readable alternative.
Reference solution
Python
def findTheDifference(s: str, t: str) -> str:
code = 0
for ch in s:
code ^= ord(ch)
for ch in t:
code ^= ord(ch)
return chr(code)Java
public static String findTheDifference(String s, String t) {
int code = 0;
for (int i = 0; i < s.length(); i++) code ^= s.charAt(i);
for (int i = 0; i < t.length(); i++) code ^= t.charAt(i);
return String.valueOf((char) code);
}C++
string findTheDifference(string s, string t) {
int code = 0;
for (char c : s) code ^= c;
for (char c : t) code ^= c;
return string(1, (char) code);
}JavaScript
var findTheDifference = function(s, t) {
let code = 0;
for (let i = 0; i < s.length; i++) code ^= s.charCodeAt(i);
for (let i = 0; i < t.length; i++) code ^= t.charCodeAt(i);
return String.fromCharCode(code);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets