Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Find the Difference solution and explanation

EasyBit ManipulationHash TableSortingString5 min read60.8% acceptanceUpdated 9 Apr 2026
Asked atGoogleBloombergAccentureAmazonMicrosoftMeta
Practise Find the Difference
11:24
Find the Difference - Leetcode 389 - PythonNeetCodeIO · 11:24 · 14K viewsWatch on YouTube
9 more videos on this problem
  1. Find the Difference - Leetcode 389 - PythonNeetCodeIO · 11:24 · 14K views
  2. Find the Difference | LeetCode problem 389Technosage · 4:49 · 11K views
  3. Find the Difference | LeetCode 389 | C++, Java, Python | BITWISE operationKnowledge Center · 6:43 · 6K views
  4. Find the Difference | LeetCode 389 | Explained 3 ApproachesProgramming Tutorials · 11:54 · 2K views
  5. Find the Difference - LeetCode 389 - Python [O(n) time and O(1) Space!]Deepti Talesra · 2:52 · 2K views
  6. Leetcode | 389. Find the difference | Easy | Java SolutionDeveloper Docs · 5:16 · 2K views
  7. Find the Difference with HashMap solution - LeetCode #389 | Python, JavaScript, Java, C++CodingNinja · 5:27 · 2K views
  8. Leetcode 389. Find the Difference [Java] | GOOGLE coding interview questionif else statement · 3:43 · 1K views
  9. find the difference | find the difference leetcode | leetcode 389 | two solutionsNaresh Gupta · 3:55 · 1K views
  10. 389. Find the Difference | LEETCODE EASYcode Explainer · 3:47 · 800 views

The problem

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

  • 0 <= s.length <= 1000
  • t.length == s.length + 1
  • s and t consist of lowercase English letters.

Approach overview

Problem Overview: You are given two strings s and t. String t is created by shuffling s and adding one extra character. Your task is to return that additional character. The challenge is identifying the extra element efficiently without expensive comparisons.

Approach 1: Frequency Count Approach (O(n) time, O(1) space)

This approach counts how many times each character appears in both strings. Use a fixed-size frequency array or a hash map from the hash table pattern. First iterate through s and increment counts. Then iterate through t and decrement counts. The moment a count becomes negative, that character is the extra one. This works because every character from s cancels out except the additional one in t. The method is straightforward and easy to implement across languages.

Approach 2: XOR Approach (O(n) time, O(1) space)

XOR exploits the property that a ^ a = 0 and a ^ 0 = a. XOR every character from both strings together. Characters that appear in both strings cancel out, leaving only the extra character. Iterate through s and t, XOR their ASCII values into a single variable, then convert the result back to a character. This technique uses constant space and avoids any auxiliary data structures. It is a classic bit manipulation trick often expected in interviews.

Approach 3: Sorting and Comparing (O(n log n) time, O(1) extra space)

Sort both strings and scan them from left to right. The first position where characters differ reveals the extra character in t. If all characters match during the scan, the extra character is the final element in the sorted t. Sorting simplifies the comparison logic but increases time complexity due to the sorting step. This approach mainly demonstrates understanding of ordering techniques from sorting.

Recommended for interviews: The XOR approach is typically preferred. It runs in linear time, constant space, and demonstrates familiarity with bit manipulation tricks. The frequency count method is also acceptable and often easier to reason about during discussion. Sorting works but is rarely considered optimal.

Approach 1: Frequency Count Approach

This approach involves creating frequency counts for both strings. Loop through each character in both strings, updating a counter for each character. By comparing these counters, you can determine which character has a different count, revealing the additional character in string t.

def findTheDifference(s, t):
    count = {}
    for char in s:
        count[char] = count.get(char, 0) + 1
    for char in t:
        if count.get(char, 0) == 0:
            return char
        count[char] -= 1

print(findTheDifference("abcd", "abcde"))  # Output: e
print(findTheDifference("", "y"))  # Output: y
import java.util.HashMap;

public class FindDifference {
    public char findTheDifference(String s, String t) {
        HashMap<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) count.put(c, count.getOrDefault(c, 0) + 1);
        for (char c : t.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) - 1);
            if (count.get(c) < 0) return c;
        }
        return '\0';
    }

    public static void main(String[] args) {
        FindDifference fd = new FindDifference();
        System.out.println(fd.findTheDifference("abcd", "abcde"));  // Output: e
        System.out.println(fd.findTheDifference("", "y"));          // Output: y
    }
}
#include <iostream>
#include <unordered_map>
using namespace std;

char findTheDifference(string s, string t) {
    unordered_map<char, int> count;
    for (char c : s) count[c]++;
    for (char c : t) {
        if (--count[c] < 0) return c;
    }
    return '\0';
}

int main() {
    cout << findTheDifference("abcd", "abcde") << endl;  // Output: e
    cout << findTheDifference("", "y") << endl;  // Output: y
    return 0;
}
function findTheDifference(s, t) {
    const count = {};
    for (const char of s) {
        count[char] = (count[char] || 0) + 1;
    }
    for (const char of t) {
        if (!count[char] || count[char] === 0) return char;
        count[char]--;
    }
    return '';
}

console.log(findTheDifference('abcd', 'abcde')); // Output: e
console.log(findTheDifference('', 'y')); // Output: y
#include <stdio.h>
#include <string.h>

char findTheDifference(char* s, char* t) {
    int count[26] = {0};
    while (*s) count[*s++ - 'a']++;
    while (*t) {
        if (count[*t - 'a']-- == 0)
            return *t;
        t++;
    }
    return '\0';
}

int main() {
    printf("%c\n", findTheDifference("abcd", "abcde"));  // Output: e
    printf("%c\n", findTheDifference("", "y"));  // Output: y
    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    public char FindTheDifference(string s, string t) {
        Dictionary<char, int> count = new Dictionary<char, int>();
        foreach (char c in s) {
            if (count.ContainsKey(c)) count[c]++;
            else count[c] = 1;
        }
        foreach (char c in t) {
            if (!count.ContainsKey(c) || count[c] == 0) return c;
            count[c]--;
        }
        return '\0';
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.FindTheDifference("abcd", "abcde"));  // Output: e
        Console.WriteLine(sol.FindTheDifference("", "y"));  // Output: y
    }
}

The Python solution uses a dictionary to count the occurrences of each character in s. It then decrements this count for each character in t until an entry has a zero count, identifying the added character.

Complexity

The time complexity is O(n) since it iterates over the strings once. Space complexity is O(1) because the dictionary size is limited to a constant number of characters.

Try this approach in the editor

Approach 2: XOR Approach

This approach leverages the properties of the XOR bitwise operator. XOR'ing the same numbers results in 0 and XOR is commutative and associative, meaning the order of operations doesn't matter. By XOR'ing all characters in both strings, one additional character will be left out, since all others cancel each other out.

def findTheDifference(s, t):
    diff = 0
    for char in s + t:
        diff ^= ord(char)
    return chr(diff)

print(findTheDifference("abcd", "abcde"))  # Output: e
print(findTheDifference("", "y"))  # Output: y
public class FindDifference {
    public char findTheDifference(String s, String t) {
        char diff = 0;
        for (char c : s.toCharArray()) diff ^= c;
        for (char c : t.toCharArray()) diff ^= c;
        return diff;
    }

    public static void main(String[] args) {
        FindDifference fd = new FindDifference();
        System.out.println(fd.findTheDifference("abcd", "abcde"));  // Output: e
        System.out.println(fd.findTheDifference("", "y"));          // Output: y
    }
}
#include <iostream>
using namespace std;

char findTheDifference(string s, string t) {
    char diff = 0;
    for (char c : s) diff ^= c;
    for (char c : t) diff ^= c;
    return diff;
}

int main() {
    cout << findTheDifference("abcd", "abcde") << endl;  // Output: e
    cout << findTheDifference("", "y") << endl;  // Output: y
    return 0;
}
function findTheDifference(s, t) {
    let diff = 0;
    for (const char of s + t) {
        diff ^= char.charCodeAt(0);
    }
    return String.fromCharCode(diff);
}

console.log(findTheDifference('abcd', 'abcde')); // Output: e
console.log(findTheDifference('', 'y')); // Output: y
#include <stdio.h>

char findTheDifference(char* s, char* t) {
    char diff = 0;
    while (*s) diff ^= *s++;
    while (*t) diff ^= *t++;
    return diff;
}

int main() {
    printf("%c\n", findTheDifference("abcd", "abcde"));  // Output: e
    printf("%c\n", findTheDifference("", "y"));  // Output: y
    return 0;
}
using System;

public class Solution {
    public char FindTheDifference(string s, string t) {
        char diff = '\0';
        foreach (char c in s) diff ^= c;
        foreach (char c in t) diff ^= c;
        return diff;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.FindTheDifference("abcd", "abcde"));  // Output: e
        Console.WriteLine(sol.FindTheDifference("", "y"));  // Output: y
    }
}

The Python solution XORs each character's ASCII value in both strings. Due to the associative property of XOR, paired characters’ XOR result in 0, leaving the additional character’s ASCII value as the final result.

Complexity

Time complexity is O(n) as it processes both strings fully. Space complexity is O(1) since it only uses a numerical variable for XOR calculations.

Try this approach in the editor

Approach 3: Counting

We can use a hash table or array cnt to count the occurrence of each character in string s, then traverse string t. For each character, we subtract its occurrence in cnt. If the corresponding count is negative, it means that the occurrence of this character in t is greater than in s, so this character is the added character.

The time complexity is O(n), and the space complexity is O(|\Sigma|), where n is the length of the string, and \Sigma represents the character set. Here the character set is all lowercase letters, so |\Sigma|=26.

function findTheDifference(s: string, t: string): string {
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    for (const c of t) {
        --cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    for (let i = 0; ; ++i) {
        if (cnt[i] < 0) {
            return String.fromCharCode(i + 'a'.charCodeAt(0));
        }
    }
}
func findTheDifference(s, t string) byte {
	cnt := [26]int{}
	for _, ch := range s {
		cnt[ch-'a']++
	}
	for i := 0; ; i++ {
		ch := t[i]
		cnt[ch-'a']--
		if cnt[ch-'a'] < 0 {
			return ch
		}
	}
}
impl Solution {
    pub fn find_the_difference(s: String, t: String) -> char {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let n = s.len();
        let mut count = [0; 26];
        for i in 0..n {
            count[(s[i] - b'a') as usize] += 1;
            count[(t[i] - b'a') as usize] -= 1;
        }
        count[(t[n] - b'a') as usize] -= 1;
        char::from(b'a' + (count.iter().position(|&v| v != 0).unwrap() as u8))
    }
}
Try this approach in the editor

Approach 4: Summation

We can sum the ASCII values of each character in string t, then subtract the sum of the ASCII values of each character in string s. The final result is the ASCII value of the added character.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

function findTheDifference(s: string, t: string): string {
    return String.fromCharCode(
        [...t].reduce((r, v) => r + v.charCodeAt(0), 0) -
            [...s].reduce((r, v) => r + v.charCodeAt(0), 0),
    );
}
func findTheDifference(s string, t string) byte {
	ss := 0
	for _, c := range s {
		ss -= int(c)
	}
	for _, c := range t {
		ss += int(c)
	}
	return byte(ss)
}
impl Solution {
    pub fn find_the_difference(s: String, t: String) -> char {
        let mut ans = 0;
        for c in s.as_bytes() {
            ans ^= c;
        }
        for c in t.as_bytes() {
            ans ^= c;
        }
        char::from(ans)
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Frequency Count Approach

The time complexity is O(n) since it iterates over the strings once. Space complexity is O(1) because the dictionary size is limited to a constant number of characters.

XOR Approach

Time complexity is O(n) as it processes both strings fully. Space complexity is O(1) since it only uses a numerical variable for XOR calculations.

Counting–
Summation–

Complexity analysis

ApproachTimeSpaceWhen to Use
Frequency Count (Hash Map / Array)O(n)O(1)General solution when using hash tables or counting characters
XOR Bit ManipulationO(n)O(1)Best choice when constant space and elegant bit trick is preferred
Sorting and CompareO(n log n)O(1)Simple conceptual approach when sorting is acceptable

Frequently asked questions

Is Find the Difference easy or hard?

Find the Difference is categorized as an Easy problem. It focuses on basic string processing and simple algorithmic ideas like frequency counting or XOR cancellation, making it a common early interview practice question.

Find the Difference Python/Java solution

Python, Java, C++, C#, and JavaScript implementations typically follow either the frequency counting method or the XOR technique. Both iterate through the strings once and return the extra character detected during counting or XOR evaluation.

How to solve Find the Difference in O(n)?

Iterate through both strings and apply XOR to every character. Because identical characters cancel each other out in XOR operations, the final result will be the ASCII value of the extra character. Converting that value back to a character gives the answer in linear time.

What is the best approach for Find the Difference?

The XOR approach is typically considered the best solution. It runs in O(n) time and O(1) space while avoiding additional data structures. XOR cancels out matching characters from both strings, leaving only the extra character added to string t.

Is Find the Difference asked at Google/Amazon/Meta?

Problems involving hash tables, character counting, and XOR tricks appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying concepts are common in string manipulation interview questions.

What data structure is used in Find the Difference?

The most common data structure is a hash table or frequency array to count character occurrences. Another efficient technique avoids data structures entirely by using bit manipulation with XOR operations.

What is the time complexity of Find the Difference?

The optimal solutions run in O(n) time, where n is the length of the strings. Both the frequency count method and the XOR approach require a single pass through the characters. Sorting-based solutions take O(n log n) due to the sorting step.

Comments

Next problem · similarSingle NumberEasy
Now write it yourselfClose this page and solve Find the Difference in the editor, without looking.
Practise Find the Difference