[Easy] 389. Find the Difference

Problem Statement

You are given two strings s and t consisting of only lowercase English letters. String t is generated by randomly shuffling string s and then adding one extra letter at a random position.

Return the letter that was added to t.

Examples

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"

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

Clarification Questions

  1. Characters in s and t? Same multiset except exactly one extra character in t.
  2. Unicode? Problem says lowercase English letters only.
  3. Order? Irrelevant; we only need the extra character identity.

Analysis Process

  • Frequency: Count letters in t, subtract counts from s; the letter with count 1 extra is the answer.
  • XOR: XOR all character codes. Every letter from s appears once in s and once in t except the added letter, which appears only in t, so pairs cancel and the XOR is the added character’s code.
  • Sum: sum(ord(c) for c in t) - sum(ord(c) for c in s) works here given small alphabet and constraints (no overflow issues in Python).

Solution Options

Option 1: XOR (O(n) time, O(1) space)

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        ret = 0
        for ch in s + t:
            ret ^= ord(ch)
        return chr(ret)

Letters that appear in both strings cancel (a ^ a == 0). The extra letter in t is XORed once, so ret equals its ASCII code.

Option 2: Counter / frequency map

from collections import Counter


class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        c = Counter(t)
        for ch in s:
            c[ch] -= 1
        for ch, k in c.items():
            if k == 1:
                return ch
        return ""

Option 3: Integer sum difference

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return chr(sum(map(ord, t)) - sum(map(ord, s)))

Comparison

Approach Time Extra space Notes
XOR O(n) O(1) Elegant; no overflow concerns
Counter O(n) O(1) alphabet Very explicit
Sum diff O(n) O(1) Simple; fine in Python for this problem

Complexity Analysis

For XOR (Option 1):

  • Time: O(n) where n = len(s) + len(t) ≈ 2 s + 1
  • Space: O(1)

Common Mistakes

  • Returning int instead of a one-character str (use chr).
  • Off-by-one: t is exactly one character longer than s.