SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

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);
    
};