389. Find the Difference
On This Page
Given two strings
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.
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.
collections.Counterclass is a handy tool in Python for counting elements in a collection.
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
- Create a Counter for the string
- Iterate over each character
- Decrement the count for character
cin the Counter.
- If the count for any character becomes
-1, that character is the one added to string
- Return the character found in the previous step.
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