Find the Difference

Problem Statement

In this problem, you are presented with two strings, s and t. The second string, t, is derived from the first string, s, by shuffling its characters and then inserting an additional character at a random location. The task is to identify and return this extra character that is present in t but not in s.

Examples

Example 1

Input:

s = "abcd", t = "abcde"

Output:

"e"

Explanation:

'e' is the letter that was added.

Example 2

Input:

s = "", t = "y"

Output:

"y"

Constraints

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

Approach and Intuition

To solve the problem of finding the additional letter in t that is not in s, we can utilize several approaches based on the characteristics and constraints given:

1. Counting Method:

   • Utilize arrays or hash maps to count the frequency of each character in both strings.
   • Compare the frequencies: The character that has one extra count in t compared to s is the added character.

2. Sorting and Comparing:

   • Sort both strings s and t.
   • Compare the strings character by character. The first mismatch encountered will be the added character.

3. Bit Manipulation:

   • Use XOR operation on all characters of both strings.
   • Since XOR-ing two identical characters results in a zero and XOR is commutative and associative, all characters that appear in both strings an even number of times will cancel out.
   • The remaining character will be the one that was added in t.

Each of the methods utilizes the properties of strings and operations in unique ways, aligning with the constraints, which do not impose severe limits on the operation counts or time complexity. The length constraint (0 <= s.length <= 1000) and the fact that t is always just one character longer than s simplify the approach since we only need to identify a single differing element.

Solutions

class Solution {
    public char findExtraChar(String original, String modified) {
        char result = 0;
        for (int i = 0; i < original.length(); i++) {
            result ^= original.charAt(i);
        }
        for (int j = 0; j < modified.length(); j++) {
            result ^= modified.charAt(j);
        }
        return result;
    }
}