389. Find the Difference

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

1. Initialize two variables, s_sum and t_sum, to store the sum of ASCII values of the characters in s and t, respectively.
2. Iterate through each character in s and add the ASCII value of the character to s_sum.
3. Iterate through each character in t and add the ASCII value of the character to t_sum.
4. The difference between t_sum and s_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);
    
};