Solution: Find the Difference

Statement

Given two strings, str1 and str2, find the index of the extra character that is present in only one of the strings.

Note: If multiple instances of the extra character exist, return the index of the first occurrence of the character in the longer string.

Constraints:

• $0 \leq$ str1.length, str2.length $\leq 1000$
• Either str2.length $=$ str1.length + 1, or, str1.length $=$ str2.length + 1
• The strings consist of lowercase English letters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to first sort both the strings. Then loop over the longer string and compare both strings, character by character. Finally, when one extra character is found in the longer string which does not match with the character at the corresponding index in the other string, we break out of the loop and return the index where the comparison failed.

The time complexity of this solution would be $O(n \log n + n)$, that is $O(n \log n)$. Here, $O(n \log n)$ is the cost of sorting one of the strings. The space complexity would be $O(1)$.

Optimized approach using bitwise manipulation

This solution utilizes the bitwise XOR manipulation to single out an extra character between two strings. It uses the property of the XOR operator of excluding matching pairs and leaves the unmatched (extra) character’s ASCII value. Initially, a variable is set to $0$, and we iterate through each string, XOR the ASCII values of its characters with the variable, and store the result of each XOR operation in the same variable. Any character present in both strings cancels out because $A⊕A=0$. The unmatched character, however, does not cancel out, and its ASCII value remains in the variable after all iterations. This value represents the extra character.

The algorithm proceeds through the following steps:

1. Initialize a variable, result, with $0$ to store the XOR result.

2. Find the lengths of both strings.

3. Iterate over the characters of str1, and for each character, do the following operations:

   • Compute the ASCII value of the character.
   • Perform a bitwise XOR operation between the current value of result and the ASCII value.
   • Store the result of the bitwise XOR operation back in result.

4. Now, iterate over the characters of str2 and repeat the operations performed in step 3 for each character in str2.

5. After iterating over both strings, the result variable will correspond to the ASCII value of the extra character.

6. Find and return the index of the extra character from the string with a greater length.

The slides below illustrate how we would like the algorithm to run: