Odd String Difference

Difficulty: Easy | Acceptance: 61.90% | Paid: No Topics: Array, Hash Table, String

You are given an array of equal-length strings words. The difference string of a string word is the string formed by the difference between consecutive characters in word.

For example, the difference string of “abc” is “1-1” because:

• ‘b’ - ‘a’ = 1
• ’c’ - ‘b’ = 1

All strings in words have the same difference string except one. Find the string that has a different difference string.

• Examples
• Constraints
• Hash Map Approach
• Comparison Approach

Examples

Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation:
- The difference string of "adc" is "3-1".
- The difference string of "wzy" is "3-1".
- The difference string of "abc" is "1-1".
"abc" has a different difference string from the other two strings, so we return "abc".

Input: words = ["aaa","bob","bbb","ddd"]
Output: "bob"
Explanation:
- The difference string of "aaa" is "0-0".
- The difference string of "bob" is "1-1".
- The difference string of "bbb" is "0-0".
- The difference string of "ddd" is "0-0".
"bob" has a different difference string from the other three strings, so we return "bob".

Constraints

3 <= words.length <= 100
2 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Hash Map Approach

Intuition Calculate the difference string for each word and use a hash map to count occurrences. The odd string will be the one whose difference pattern appears exactly once.

Steps

• Create a helper function to compute the difference string (sequence of character differences)
• Iterate through all words, compute their difference strings, and store in a hash map
• Find and return the word whose difference string has a count of 1

class Solution:
    def oddString(self, words: List[str]) -> str:
        def get_diff(s):
            return tuple(ord(s[i+1]) - ord(s[i]) for i in range(len(s)-1))
        
        diff_count = {}
        for word in words:
            diff = get_diff(word)
            if diff not in diff_count:
                diff_count[diff] = []
            diff_count[diff].append(word)
        
        for diff, word_list in diff_count.items():
            if len(word_list) == 1:
                return word_list[0]
        
        return ""

Complexity

• Time: O(n × m) where n is the number of words and m is the length of each word
• Space: O(n × m) for storing difference strings in the hash map
• Notes: Simple and intuitive, uses extra space for the hash map

Comparison Approach

Intuition Compare the first two words’ difference strings. If they match, the odd string is elsewhere. If they differ, compare with the third to identify the outlier.

Steps

• Calculate difference strings for the first two words
• If they’re equal, iterate through remaining words to find the mismatch
• If they differ, use the third word’s difference to determine which of the first two is the odd one

class Solution:
    def oddString(self, words: List[str]) -> str:
        def get_diff(s):
            return tuple(ord(s[i+1]) - ord(s[i]) for i in range(len(s)-1))
        
        diff0 = get_diff(words[0])
        diff1 = get_diff(words[1])
        
        if diff0 == diff1:
            for i in range(2, len(words)):
                if get_diff(words[i]) != diff0:
                    return words[i]
        else:
            diff2 = get_diff(words[2])
            if diff2 == diff0:
                return words[1]
            else:
                return words[0]
        
        return ""

Complexity

• Time: O(n × m) where n is the number of words and m is the length of each word
• Space: O(m) for storing difference arrays
• Notes: More space-efficient as it doesn’t require a hash map, but slightly more complex logic