
Description
The problem asks to find the extra character that appears in the string t
, but not in the string s
. Both strings s
and t
contain lowercase letters, and the string t
is created by shuffling s
and adding one additional character at a random position. The task is to identify and return that extra character.
Intuition
The difference between the two strings lies in exactly one extra character that is added to t
. A simple way to identify this character is to compute the sum of the ASCII values (or Unicode code points) of the characters in both strings. Since t
contains all characters from s
along with one additional character, the difference between the sum of characters in t
and s
will give the extra character.
Approach
- Initialize two variables,
s_sum
andt_sum
, to store the sum of ASCII values of the characters ins
andt
, respectively. - Iterate through each character in
s
and add the ASCII value of the character tos_sum
. - Iterate through each character in
t
and add the ASCII value of the character tot_sum
. - The difference between
t_sum
ands_sum
will give the ASCII value of the extra character, which can then be converted back to a character and returned.
Complexity
Time Complexity:
O(n), where n
is the length of the string s
. We iterate through both strings s
and t
once, so the total time complexity is linear.
Space Complexity:
O(1), as we only use a few extra variables for the sums and the difference, regardless of the input size.
Code
C++
class Solution {
public:
char findTheDifference(string s, string t) {
int s_sum = 0, t_sum = 0;
for (char c : s) {
s_sum += int(c);
}
for (char c : t) {
t_sum += int(c);
}
return char(t_sum - s_sum);
}
};
Python
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
s_sum = sum(ord(c) for c in s)
t_sum = sum(ord(c) for c in t)
return chr(t_sum - s_sum)
Java
class Solution {
public char findTheDifference(String s, String t) {
int s_sum = 0, t_sum = 0;
for (char c : s.toCharArray()) {
s_sum += (int) c;
}
for (char c : t.toCharArray()) {
t_sum += (int) c;
}
return (char) (t_sum - s_sum);
}
}
JavaScript
var findTheDifference = function(s, t) {
let s_sum = 0;
let t_sum = 0;
for(let i of s){
s_sum += i.charCodeAt(0);
}
for(let i of t){
t_sum += i.charCodeAt(0);
}
return String.fromCharCode(t_sum- s_sum);
};