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)$ ...