You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
Example 1:
Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter that was added.
Example 2:
Input: s = "", t = "y" Output: "y"
Constraints:
0 <= s.length <= 1000t.length == s.length + 1s and t consist of lowercase English letters.In #389 Find the Difference, you are given two strings where t is created by shuffling s and adding one extra character. The task is to determine which character was added. Since the strings are small and consist of characters, several efficient strategies can be used.
A common method uses a hash table (or frequency array). Count the occurrences of each character in s, then iterate through t and find the character whose frequency exceeds the expected count. This works well because it tracks differences in frequency directly.
An even more elegant approach uses bit manipulation with XOR. XOR all characters from both strings together; identical characters cancel out, leaving only the extra one. This results in O(n) time and O(1) space.
Another alternative is sorting both strings and comparing them character by character until a mismatch is found. While simple to implement, it incurs a higher O(n log n) time complexity due to sorting.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table / Frequency Count | O(n) | O(1) |
| XOR Bit Manipulation | O(n) | O(1) |
| Sorting and Compare | O(n log n) | O(1) |
Kevin Naughton Jr.
This approach involves creating frequency counts for both strings. Loop through each character in both strings, updating a counter for each character. By comparing these counters, you can determine which character has a different count, revealing the additional character in string t.
The time complexity is O(n) where n is the length of s as we iterate over t once in the worst case. Space complexity is O(1) because the storage requirement is constant (the fixed size count array).
1import java.util.HashMap;
2
3public class FindDifference {
4 public char findTheDifference(String s, String t) {
5
This solution utilizes a HashMap to keep a frequency count of the characters in string s. For each character in t, it decreases the count and checks for a character whose count becomes negative, which indicates it's the extra character.
This approach leverages the properties of the XOR bitwise operator. XOR'ing the same numbers results in 0 and XOR is commutative and associative, meaning the order of operations doesn't matter. By XOR'ing all characters in both strings, one additional character will be left out, since all others cancel each other out.
Time complexity is O(n) as both strings are traversed. Space complexity is O(1) because only a single variable is used.
1
public class Solution {
public char FindTheDifference(string s, string t) {
char diff = '\0';
foreach (char c in s) diff ^= c;
foreach (char c in t) diff ^= c;
return diff;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.FindTheDifference("abcd", "abcde")); // Output: e
Console.WriteLine(sol.FindTheDifference("", "y")); // Output: y
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, both strings can be sorted and compared character by character. The first mismatch indicates the extra character. However, sorting increases the time complexity to O(n log n), making it less efficient than XOR or hashing.
Yes, this problem is a common beginner-level interview question because it tests understanding of strings, hashing, and bit manipulation. Variations of this concept may appear in interviews at large tech companies.
A hash table or frequency array is commonly used to track character counts from the first string. When scanning the second string, any excess frequency reveals the added character. This approach is straightforward and runs in linear time.
The most optimal approach uses XOR bit manipulation. By XORing all characters from both strings, matching characters cancel out and only the extra character remains. This runs in O(n) time with O(1) extra space.
This C# approach uses a combined XOR across characters in both strings. An extra character will remain uniquely due to its unmatched presence.