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:

  • 00 \leq str1.length, str2.length 1000\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(nlogn+n)O(n \log n + n), that is O(nlogn)O(n \log n). Here, O(nlogn)O(n \log n) is the cost of sorting one of the strings. The space complexity would be O(1)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 00 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:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.