algoadvance

LeetCode 389 - Find the Difference

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

Example:

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

Constraints:

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

Clarifying Questions

1. Can the newly added letter appear anywhere in the string t?
   • Yes, it can appear at any position.
2. Should we consider the case sensitivity of the characters?
   • No, the characters are lowercase English letters as stated in constraints.

Strategy

To solve this problem, we can use the following approaches:

Approach 1: Counting with Hash Maps

We’ll count the frequency of each character in both strings s and t. The character that has a higher count in t than in s is the added character.

Approach 2: Sum of ASCII Values

Calculate the sum of ASCII values of the characters in s and t. The difference between the two sums will be the ASCII value of the added character.

Approach 3: XOR Operation

We can use bitwise XOR to solve this problem. When two identical bits are XOR’d, the result is 0. Hence, XOR of all characters in s and t will cancel out identical characters, and the result will be the added character.

Time Complexity

All the approaches are efficient, but the XOR approach is both time-efficient and space-efficient.

• Time Complexity: O(n), where n is the length of string s.
• Space Complexity: O(1), minimal extra space is used because we only need a few variables.

Code

We’ll implement the XOR approach here:

def findTheDifference(s: str, t: str) -> str:
    result = 0
    for char in s:
        result ^= ord(char)
    for char in t:
        result ^= ord(char)
    return chr(result)

# Test Case
print(findTheDifference("abcd", "abcde"))  # Output: "e"

Explanation of Code

1. Initialize result to 0.
2. XOR all characters in string s with result.
3. XOR all characters in string t with result.
4. The final value of result will be the ASCII value of the added character.
5. Convert this ASCII value back to the corresponding character using chr() function and return it.

This solution efficiently finds the extra character with linear time complexity and constant space complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?