Find the Difference Solution in Java

Problem Description

So, you’ve got two strings, s and t. One of them is like that friend who always shows up with a surprise gift, while the other is just a plain old string. The catch? The surprise gift string t has one extra character compared to s. Your mission, should you choose to accept it, is to find that extra character. It’s like playing hide and seek, but the seeker is you, and the hider is a sneaky little character that just can’t resist being different!

Imagine you’re at a party, and everyone is wearing the same outfit. Suddenly, you spot that one person who decided to wear a neon green tutu. Your task is to identify that unique individual. In this case, the neon green tutu is the extra character in string t.

Code Solution


class Solution {
  public char findTheDifference(String s, String t) {
    final char sXors = (char) s.chars().reduce(0, (a, b) -> a ^ b);
    final char tXors = (char) t.chars().reduce(0, (a, b) -> a ^ b);
    return (char) (sXors ^ tXors);
  }
}

Approach

The approach used in the code is quite clever. It utilizes the XOR bitwise operation to find the unique character. Here’s how it works:

It computes the XOR of all characters in string s and stores it in sXors.
It does the same for string t and stores it in tXors.
Finally, it XORs sXors and tXors together. The result will be the extra character in t because all other characters will cancel each other out.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the longer string `t`.
Space Complexity	O(1), as we are using a constant amount of space for the XOR calculations.

Real-World Example

Let’s say you’re at a family reunion, and everyone is wearing a blue shirt. But your cousin decided to wear a bright red shirt because they thought it would make them stand out. In this scenario, the blue shirts represent string s, and the red shirt represents the extra character in string t. Your task is to identify that one cousin who decided to be different, just like the extra character in the string!