💬 Discord
Sign In
NeetCode #861LC-389EasyBit Manipulation
← Back to All Problems

#861 · #389 · Find the Difference(找不同)

📌 Problem Statement & Constraints

You are given two strings s and t. String t is produced by shuffling s and then inserting one extra lowercase letter at a random position. Return that extra letter. Constraints: 0 <= s.length <= 1000, t.length == s.length + 1, and both contain only lowercase English letters.

💡 Core Algorithmic Approaches

  1. Every character of s also appears in t, plus exactly one extra character.
  2. XOR-ing the character codes of all of s and all of t cancels the shared characters, leaving only the extra one.
  3. This mirrors the single-number trick and avoids any extra data structure.
  4. An equally valid alternative is to compare the sums of the character codes, or to use a 26-entry count array.

💻 Benchmark Python3 Implementation

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        res = 0
        for ch in s:
            res ^= ord(ch)              # shared characters cancel out
        for ch in t:
            res ^= ord(ch)
        return chr(res)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over each string.
💾 Space Complexity
O(1): a single accumulator.

⚠️ Interview Pitfalls & Follow-ups

  • Using a set difference: sets discard duplicates, so a repeated extra character would be lost; e.g. s = a, t = aa.
  • Sorting both strings and comparing: O(n log n) and more code than the XOR pass.
  • Forgetting the empty-string case: s may be empty, in which case the single character of t is the answer; the loops handle it.
  • XOR-ing characters instead of their codes: in Python you must call ord explicitly, since strings are not integers.