Find the Difference
EasyPrompt
Approaches
4 approaches with complexity analysis and trade-offs.
This approach relies on sorting. If we sort the characters of both strings, they will be identical up to the length of the original string s. By comparing the sorted strings character by character, the first mismatch we find will reveal the extra letter added to t. If all characters match up to the end of s, the extra character must be the very last character of the sorted t.
Algorithm
- Convert both strings
sandtinto character arrays, let's call themsCharsandtChars. - Sort both
sCharsandtCharsalphabetically. - Iterate from the first character up to the length of
s. - In each iteration, compare
sChars[i]withtChars[i]. - If the characters at the current index
iare different,tChars[i]is the added character, so return it. - If the loop completes without finding any difference, it means the extra character is the last character in
tChars. ReturntChars[t.length() - 1].
Walkthrough
The core idea is that after sorting, two identical sets of characters would result in identical arrays. Since t has one extra character, its sorted version will be identical to s's sorted version until the point where the extra character is positioned, or the extra character will be appended at the end.
import java.util.Arrays; class Solution { public char findTheDifference(String s, String t) { char[] sChars = s.toCharArray(); char[] tChars = t.toCharArray(); Arrays.sort(sChars); Arrays.sort(tChars); for (int i = 0; i < sChars.length; i++) { if (sChars[i] != tChars[i]) { return tChars[i]; } } // If the loop finishes, the extra character is the last one in t return tChars[tChars.length - 1]; }}Complexity
Time
O(N log N), where N is the length of the string `t`. The dominant operation is sorting the character arrays.
Space
O(N), where N is the length of the string `t`. This space is required to store the character arrays for sorting. Some sorting algorithms might use additional space (e.g., `O(log N)` for quicksort's recursion stack).
Trade-offs
Pros
The logic is straightforward and easy to understand.
Cons
The time complexity of
O(N log N)is suboptimal for this problem.It requires extra space to hold the character arrays, which can be
O(N).
This method involves counting the frequency of each character. We can use a hash map (or a simple array if the character set is fixed, like 26 lowercase letters) to store the character counts of the original string s. Then, we iterate through the modified string t. When we encounter a character that is not in our frequency map or whose count is already zero, we have found the added letter.
Algorithm
- Create a hash map to store character frequencies.
- Iterate through the original string
sand for each character, increment its count in the hash map. - Iterate through the modified string
t. For each character int:- Check if the character is in the map and its count is greater than 0.
- If it is, decrement the count.
- If the character is not in the map or its count is already 0, this must be the added character. Return it.
Walkthrough
By first counting all characters in s, we establish a baseline. Then, as we iterate through t, we effectively 'remove' each character we see from our baseline counts. The character in t that cannot be removed (because it wasn't in s at all, or we've already seen all instances of it from s) is our answer.
For a character set limited to lowercase English letters, an array of size 26 can be used instead of a hash map for slightly better performance.
import java.util.HashMap;import java.util.Map; class Solution { public char findTheDifference(String s, String t) { Map<Character, Integer> map = new HashMap<>(); // Populate map with character counts from s for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } // Decrement counts for characters in t for (char c : t.toCharArray()) { int count = map.getOrDefault(c, 0); if (count == 0) { // This character is the extra one return c; } else { map.put(c, count - 1); } } // This line should not be reachable given the problem constraints return ' '; }}Complexity
Time
O(N), where N is the length of string `t`. We iterate through both strings once, and hash map operations take, on average, O(1) time.
Space
O(K), where K is the number of unique characters in the string. If the character set is fixed (e.g., ASCII or 26 lowercase letters), this can be considered O(1).
Trade-offs
Pros
Achieves linear time complexity, which is a significant improvement over sorting.
It's a versatile approach that works for any character set.
Cons
Has some overhead associated with hash map operations (calculating hash codes, handling potential collisions).
Uses more space than the most optimal solutions, especially if the character set is large.
This is a clever mathematical approach. Since t is composed of all characters from s plus one extra character, the sum of the character codes (like ASCII values) of t will be exactly the sum of character codes of s plus the code of the added character. By finding the difference between the two sums, we can identify the added character.
Algorithm
- Initialize an integer variable,
charSum, to 0. - Iterate through the characters of string
tand add the ASCII (or Unicode) value of each character tocharSum. - Iterate through the characters of string
sand subtract the ASCII (or Unicode) value of each character fromcharSum. - The final value of
charSumwill be the ASCII value of the added character. - Cast this integer value back to a
charand return it.
Walkthrough
We can find the result in a single pass. We can start with the character code of the last character in t (since t is one character longer than s) and then iterate from 0 to s.length() - 1, adding the character code from t and subtracting the one from s in each step. This avoids two separate loops.
class Solution { public char findTheDifference(String s, String t) { int sumS = 0; int sumT = 0; for (char c : s.toCharArray()) { sumS += c; } for (char c : t.toCharArray()) { sumT += c; } return (char)(sumT - sumS); }}Complexity
Time
O(N), where N is the length of string `t`. We need to iterate through both strings once.
Space
O(1), as we only need a few variables to store the sums, regardless of the input size.
Trade-offs
Pros
Very efficient with O(N) time complexity and O(1) space complexity.
Extremely simple and concise to implement.
Cons
There is a theoretical, though highly unlikely, risk of integer overflow if the strings are extremely long and use characters with large Unicode values.
This is a highly elegant and efficient solution that uses the properties of the bitwise XOR operator. The XOR operation has the property that x ^ x = 0 and x ^ 0 = x. If we XOR all characters from both strings together, every character that is common to both s and t will appear twice in the operation, effectively canceling itself out (e.g., c ^ c = 0). The only character that doesn't get canceled is the one that was added to t.
Algorithm
- Initialize a character or integer variable,
result, to 0. - Iterate through each character of string
sand perform a bitwise XOR operation between the character andresult. - Iterate through each character of string
tand perform a bitwise XOR operation between the character andresult. - The final value of
resultwill be the added character.
Walkthrough
The beauty of this approach is that the order of operations doesn't matter due to the commutative and associative properties of XOR. We can combine the two loops into one for a more compact implementation. The result is a robust, single-pass solution with minimal space usage.
Example: s = "ab", t = "bac"
result = ('a' ^ 'b') ^ ('b' ^ 'a' ^ 'c')
result = ('a' ^ 'a') ^ ('b' ^ 'b') ^ 'c'
result = 0 ^ 0 ^ 'c'
result = 'c'
class Solution { public char findTheDifference(String s, String t) { char result = 0; for (char c : s.toCharArray()) { result ^= c; } for (char c : t.toCharArray()) { result ^= c; } return result; }}Complexity
Time
O(N), where N is the length of string `t`, as we iterate through both strings once.
Space
O(1), as it only requires a single variable to store the accumulated XOR value.
Trade-offs
Pros
Achieves optimal O(N) time and O(1) space complexity.
Avoids the potential integer overflow issue of the summation method.
It's a common and powerful technique for problems involving finding a unique element in a set.
Cons
The concept of bitwise XOR might be less intuitive for beginners compared to direct counting or summation.
Solutions
Solution
class Solution { public char findTheDifference ( String s , String t ) { int [] cnt = new int [ 26 ]; for ( int i = 0 ; i < s . length (); ++ i ) { ++ cnt [ s . charAt ( i ) - 'a' ]; } for ( int i = 0 ;; ++ i ) { if (-- cnt [ t . charAt ( i ) - 'a' ] < 0 ) { return t . charAt ( i ); } } } }class Solution: def findTheDifference(self, s: str, t: str) -> str: cnt = Counter(s) for c in t: cnt[c] -= 1 if cnt[c] < 0: return cclass Solution { public: char findTheDifference ( string s , string t ) { int cnt [ 26 ]{}; for ( char & c : s ) { ++ cnt [ c - 'a' ]; } for ( char & c : t ) { if ( -- cnt [ c - 'a' ] < 0 ) { return c ; } } return ' ' ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.