We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Odd String Difference

Difficulty: Easy

Problem Description

You are given an array of equal-length strings words. Each string can be converted into a difference integer array where difference[i][j] = words[i][j+1] - words[i][j]. All strings in words have the same difference integer array, except one. You should find that string.

Key Insights

  • Each string generates a difference array based on the differences in their character positions in the alphabet.
  • All strings except one will produce the same difference array.
  • The task is to identify the string that produces a unique difference array.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of strings and n is the length of each string.
Space Complexity: O(m) for storing the difference arrays.

Solution

To solve the problem, we will:

  1. Create a function to calculate the difference integer array for a given string.
  2. Use a hash table (or dictionary) to count occurrences of each difference array.
  3. Identify the difference array that occurs only once and return the corresponding string.

Code Solutions

def oddString(words):
    def get_difference_array(word):
        return [ord(word[i + 1]) - ord(word[i]) for i in range(len(word) - 1)]

    difference_map = {}
    for word in words:
        diff = tuple(get_difference_array(word))
        if diff in difference_map:
            difference_map[diff].append(word)
        else:
            difference_map[diff] = [word]

    for diff, word_list in difference_map.items():
        if len(word_list) == 1:
            return word_list[0]
← Back to All Questions