389. Find the Difference

LeetCode problem 389

Problem Statement

Given two strings s and t, the string t is generated by shuffling the characters of s and adding one additional character at a random position. The task is to identify and return that extra character.

Naive Solution

A naive solution would involve comparing the characters in both strings one by one to detect the extra character in t. This method is not efficient as it could take a linear amount of time for strings of considerable lengths.

Hints & Tips

• Counting occurrences of characters can help detect discrepancies.
• The collections.Counter class is a handy tool in Python for counting elements in a collection.

Approach

We can utilize Python’s collections.Counter to help us find the difference between the two strings. The Counter allows us to quickly count the occurrences of each character in the string s. We then iterate over the string t and decrement the count for each character encountered. The character that results in a count of -1 is the one that was added to t.

Steps

1. Create a Counter for the string s.
2. Iterate over each character c in string t.
3. Decrement the count for character c in the Counter.
4. If the count for any character becomes -1, that character is the one added to string t.
5. Return the character found in the previous step.

Solution

from collections import Counter

class Solution:
  def findTheDifference(self, s: str, t: str) -> str:
    count = Counter(s)

    for c in t:
      count[c] -= 1
      if count[c] == -1:
        return c