We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Difference

Number: 389

Difficulty: Easy

Paid? No

Companies: Google, Meta, Bloomberg, Amazon, Apple, Microsoft, Accenture

Problem Description

You are given two strings s and t. String t is generated by randomly shuffling string s and then adding one extra letter at a random position. The task is to return the extra letter that was added to t.

Key Insights

  • The problem guarantees that t has exactly one more character than s.
  • Each character in s appears in t, except for the one additional character.
  • Using XOR: XORing all characters in s and t cancels out the common ones, leaving the extra character.
  • Alternative approaches include using a hash table (frequency counting) or sorting both strings.

Space and Time Complexity

Time Complexity: O(n), where n is the length of string t. Space Complexity: O(1) when using the XOR or summation method.

Solution

We can solve this problem efficiently using the XOR operation. The idea is that XORing a number with itself cancels out to zero. By XORing the ASCII codes of all characters in s and t, the characters that occur in both will cancel out, leaving only the ASCII code of the additional character. This approach uses constant space and runs in linear time.

Code Solutions

# Python solution using XOR
def findTheDifference(s: str, t: str) -> str:
    result = 0
    # XOR all characters in s
    for char in s:
        result ^= ord(char)
    # XOR all characters in t; the extra character will remain
    for char in t:
        result ^= ord(char)
    # Convert the remaining ASCII code back to a character
    return chr(result)

# Example usage:
s = "abcd"
t = "abcde"
print(findTheDifference(s, t))  # Expected output: "e"
← Back to All Questions