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#

An optimized approach to solve this problem is using the bitwise manipulation technique. We use the bitwise XOR operation to identify the extra character from one of the strings and return the index of that 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:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

Let’s start with the simplest step:

Initialize a variable result with 0. Find the lengths of both strings. Iterate over each character of str1, and for each character, perform a bitwise XOR operation between the current value of result and the ASCII value of the character. Update the result with the computed XOR value every time.

Similar to the first step, now iterate over each character of the str2, and for each character, perform the bitwise XOR operation between the current value of the result and the ASCII value of the character. Again, update the result variable with the computed XOR value every time. After the traversals of both strings, result will contain the ASCII value of the extra character.

This technique works because XOR returns $0$ if the bits are the same (both $0$ or both $1$) and $1$ if the bits differ (one is $0$, and the other is $1$). For example, $111 \space XOR \space 111$ returns $000$, and $101 \space XOR \space 010$ returns $111$. Keeping this property in mind, when we traverse the str2, the common characters between the str1 and str2 cancel out, leaving only the extra character in the result variable.

Now, we have the ASCII value of the extra character in the result variable. To find the index of this extra character, we check the length of both strings. Since the extra character is present in the longest string, we return the index of that extra character from the longest string.

Just the code#

Here’s the complete solution to this problem:

Solution summary#

To recap, the solution to this problem can be divided into the following three parts:

1. Intialize a variable, result, with $0$.

2. Perform a bitwise XOR operation between the current value of result and the ASCII value of each character in str1. Update the value of result with the computed XOR value every time.

3. Perform a bitwise XOR operation between the current value of result and the characters of str2. Update the value of result each time with the computed XOR value.

4. result now contains the ASCII value of the extra character. Find and return the index of the extra character from the longer string.

Time complexity#

The time complexity of the solution is $O(n)$, where $n$ is the length of the longest string.

Space complexity#

The space complexity of the solution above is $O(1)$, because we used a constant amount of space.