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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Difference

Difficulty: Easy

Problem Description

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

Key Insights

  • The length of string t is exactly one greater than the length of string s.
  • The additional letter can be found by comparing the characters of both strings.
  • We can utilize hash tables or bit manipulation for an efficient solution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (if using bit manipulation) or O(n) (if using a hash table)

Solution

To solve the problem, we can use two main approaches:

  1. Using a Hash Table: We can count the occurrences of each character in both strings s and t. The character that has a count difference of one will be the added character.

  2. Using Bit Manipulation: We can utilize the XOR operation. By XORing all characters in both strings, the characters that appear in both will cancel each other out, leaving us with the unique character that was added.

Both approaches are efficient and straightforward.

Code Solutions

def findTheDifference(s: str, t: str) -> str:
    # Using XOR to find the added character
    result = 0
    for char in s:
        result ^= ord(char)  # XOR all characters in s
    for char in t:
        result ^= ord(char)  # XOR all characters in t
    return chr(result)  # Convert the resulting integer back to a character
← Back to All Questions