Odd String Difference

You are given an array of strings called “words”. Each string in this array has the same length, let’s call it “n”.
You can create an “integer difference array” from each string in the following way: For each pair of adjacent letters in the string, calculate the difference between their alphabetical positions and store it in the array. For example, for the string “abc”, the difference array is [1, 1] because ‘b’ is one position after ‘a’, and ‘c’ is one position after ‘b’. Note that we are considering the position of ‘a’ as 0, ‘b’ as 1, and so on until ‘z’ as 25.
All strings in the input array have the same difference array, except one string. This one string’s difference array doesn’t match with others. Your task is to find and return this “odd” string.

For example, consider the input [“adc”,“wzy”,“abc”]. The difference arrays for the three words are:

“adc” –> [3, -1] because ’d’ is 3 positions after ‘a’, and ‘c’ is 1 position before ’d’.
“wzy” –> [3, -1] because ‘z’ is 3 positions after ‘w’, and ‘y’ is 1 position before ‘z’.
“abc” –> [1, 1] because ‘b’ is 1 position after ‘a’, and ‘c’ is 1 position after ‘b’.

Here, “abc” is the “odd” string because its difference array [1, 1] is different from the others, which are [3, -1]. So, the function should return “abc”.

In this problem, you are given a list of words. Each word can be transformed into a difference array where each element is the difference between the position of the next character and the current character in the English alphabet. Your task is to find the word that has a different difference array from the rest.

To solve this problem, you need to:

Create a function that transforms a word into a difference array.
Transform each word in the input list into its corresponding difference array.
Since all words but one have the same difference array, find the one that’s different.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def oddString(self, words: List[str]) -> str:
        # Helper function to calculate difference array
        def diff(word):
            differences = []
            for i in range(len(word) - 1):
                difference = ord(word[i+1]) - ord(word[i])
                differences.append(difference)
            return differences

        # Calculate difference array for all words
        diffs = []
        for word in words:
            word_diff = diff(word)
            diffs.append(word_diff)

        # Find and return the odd word out
        for i in range(len(words)):
            if diffs.count(diffs[i]) == 1:
                return words[i]

The diff() helper function transforms a word into a difference array by subtracting the ASCII value (i.e., position in the alphabet) of the current character from the next character. It then creates the diffs list, which stores the difference array of each word in words. Finally, it iterates over diffs and returns the first word whose difference array only appears once in diffs (i.e., the word that has a different difference array from the rest).

Improvement #1

Instead of creating difference arrays for all the strings in one go, the approach is to look at one difference at a time and find the “odd” string.

Let’s walk through this:

You start by looking at the difference in position between the first and second letters in all the strings.
You store these differences in a dictionary. The key is the difference, and the value is a list of string indices where this difference occurs.
If there’s a case where exactly two different differences occur, it means that you’ve found a place where the “odd” string differs from the rest.
By looking at which difference occurs only once, you can find the index of the “odd” string and return it.

In this way, you can find the “odd” string by only looking at one difference at a time.

Why is this helpful? This approach allows you to potentially find the “odd” string more quickly. Instead of calculating all the differences for all the strings at once, you can stop as soon as you find the “odd” string. This could save you some computation, especially if the “odd” string differs from the rest at an early position.

So, it’s like looking for a mismatch one step at a time, instead of finding all the matches first and then looking for the one that doesn’t fit.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# calculate idx([1] - [0]) for each word, 
# if the size of map increases to 2, that means we have a word, for which its idx([1] - [0]) is not equal to that of others, 
# then check the size of the vector in map's 1st and 2nd int, whichever is 1, contains our answer word.
# generalize this for idx([j + 1] - [j])
class Solution:
    def oddString(self, words: List[str]) -> str:

        for char_index in range(1, len(words[0])):
            hashmap = collections.defaultdict(list)

            for i, word in enumerate(words):
                hashmap[ord(word[char_index]) - ord(word[char_index - 1])].append(i)

            if len(hashmap) >= 2:
                for key, val in hashmap.items():
                    if len(val) == 1:
                        return words[val[0]]

        return words[0]

Improvement #2

O(1) space:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def oddString(self, words: List[str]) -> str:
        for j in range(1, len(words[0])):        
            hashmap = collections.defaultdict(list)

            for i, word in enumerate(words):
                if len(hashmap[ord(word[j]) - ord(word[j-1])]) <= 1:
                    hashmap[ord(word[j]) - ord(word[j-1])].append(i)

            if len(hashmap) >= 2:
                for key, val in hashmap.items():
                    if len(val) == 1:
                        return words[val[0]]

        return words[0]