Find the Difference

Easy
433.

Find the Difference

Find the Difference is an easy coding problem on strings, hash table and sorting, asked in Amazon, Google and Bloomberg interviews.

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 <= 39
  • t.length == s.length + 1
  • Both consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var findTheDifference = function(s, t) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 39
  • t.length == s.length + 1
  • Both consist of lowercase English letters.

Hints for Find the Difference

  1. Hint 1

    Counting letters in both strings and finding the surplus works and is easy to read.

  2. Hint 2

    Slicker: XOR the character codes of every letter in both strings.

  3. 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

  1. XOR all codes of s and t into one accumulator.
  2. 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