FindtheDifference389.java

/*
 * Problem: 389. Find the Difference
 *
 * Problem Statement:
 * You are given two strings s and t. String t is generated by random shuffling string s 
 * and then adding one more letter at a random position. Return the letter that was added to t.
 *
 * Intuition:
 * Since string t contains every character from string s plus exactly one additional character, 
 * we can isolate the extra character by using mathematical or bitwise operations that 
 * "cancel out" the common characters.
 *
 * Approach:
 * 1. Summation Method: Calculate the sum of ASCII values for all characters in s and t. 
 *    The difference (sum_t - sum_s) will be the ASCII value of the extra character.
 * 2. XOR Method: XORing a value with itself results in 0 (x ^ x = 0), and XORing with 0 
 *    returns the value (x ^ 0 = x). XORing all characters in both strings will cancel 
 *    out the pairs, leaving only the added character.
 *
 * Time Complexity: O(N), where N is the length of string t. We iterate through both strings once.
 * Space Complexity: O(N) in this implementation because toCharArray() creates a new array. 
 *                  It could be O(1) if we used s.charAt(i) instead.
 *
 * Edge Cases:
 * - s is empty: t will have exactly one character, which is the result.
 * - The extra character is a duplicate of one already in s.
 *
 * Dry Run:
 * s = "ae", t = "aea"
 * Sum Method: sum1 = 97+101=198, sum2 = 97+101+97=295. 295 - 198 = 97 ('a').
 * XOR Method: 0 ^ 'a' ^ 'e' ^ 'a' ^ 'e' ^ 'a' = ('a'^'a') ^ ('e'^'e') ^ 'a' = 0 ^ 0 ^ 'a' = 'a'.
 *
 * Correctness Check:
 * The logic is sound. Using 'long' for the sum prevents overflow for very long strings, 
 * though for standard LeetCode constraints, 'int' is usually sufficient.
 */
class FindtheDifference389{
    public char findTheDifference(String s, String t) {
        // Use long to store the sum of ASCII values to prevent potential overflow
        long sum1=0,sum2=0;
        // Convert strings to arrays to facilitate iteration
        char[] arr1=s.toCharArray();
        char[] arr2=t.toCharArray();
        
        // Accumulate the total ASCII value of the original string s
        for(char i:arr1){
            sum1+=(long)i;
        }
        // Accumulate the total ASCII value of the modified string t
        for(char i:arr2){
            sum2+=(long)i;
        }
        // The difference between the two sums is the ASCII value of the added character
        return (char)(sum2-sum1);
    }

    public char findTheDifference1(String s, String t) {
        // Initialize XOR accumulator to 0 (the identity element for XOR)
        char c = 0;
        // XOR every character in string s
        for(char cs : s.toCharArray()) c ^= cs;
        // XOR every character in string t; common characters will cancel out to 0
        for(char ct : t.toCharArray()) c ^= ct;
        
        // The remaining value in c is the character that did not have a pair
        return c;
    }
}