Code Logo

Find the Difference

Published at23 Jul 2026
Created by
Easy 0 views
Like0

You are given two strings s and t. String t is generated by randomly shuffling string s and then adding one more character at a random position. Find the character that was added to t.

A hash map solution counts characters in s, then decrements for characters in t. The character that has a count of -1 (or the one remaining after decrementing) is the added character. Alternatively, XOR of all characters in both strings cancels out the duplicates, leaving the added character.

For example, s = "abcd", t = "abcde" → the added character is 'e'.

The XOR approach (s XOR t) is more space-efficient at O(1), but the hash map approach is more generally applicable to problems where characters are not guaranteed to be letters. Both are valid solutions.

The XOR approach works because XOR of two identical values cancels out (a XOR a = 0). By XORing all characters in both strings, the duplicate characters cancel and only the added character remains. This uses O(1) space. However, the hash map approach is more general and works for any character set, not just lowercase letters.

The problem guarantees that t always contains exactly one extra character compared to s. Both strings consist only of lowercase English letters.

Example Input & Output

Example 1
Input
"", "y"
Output
"y"
Explanation

Single char added.

Example 2
Input
"abcd", "abcde"
Output
"e"
Explanation

e is added.

Example 3
Input
"a", "aa"
Output
"a"
Explanation

Extra a added.

Algorithm Flow

Recommendation Algorithm Flow for Find the Difference
Recommendation Algorithm Flow for Find the Difference

Solution Approach

Count chars in s, decrement for t. The char with remaining count is the extra one.

function solution(s, t) {
  var counts = {};
  for (var i = 0; i < s.length; i++) counts[s[i]] = (counts[s[i]] || 0) + 1;
  for (var i = 0; i < t.length; i++) {
    if (!counts[t[i]]) return t[i];
    counts[t[i]]--;
  }
  return "";
}

Time O(n), Space O(1).

Best Answers

java
import java.util.*;
class Solution {
    public char solution(String s, String t) {
        int[] counts = new int[26];
        for (char ch : s.toCharArray()) counts[ch - 'a']++;
        for (char ch : t.toCharArray()) {
            if (--counts[ch - 'a'] < 0) return ch;
        }
        return ' ';
    }
}