#2451

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Odd String Difference

Identify the one string in an array whose consecutive letter differences deviate from all others using array scanning plus hash lookup.

array hash table string

Problem Statement

Given an array of equal-length lowercase strings words, each string can be converted into an integer difference array where each element is the difference between consecutive letters in the alphabet. Most strings share the same difference array, except one which is unique.

Your task is to find and return the string whose difference array does not match the others. For example, in words = ["adc","wzy","abc"], "abc" is the outlier because its difference array differs from the rest.

Examples

Example 1

Input: words = ["adc","wzy","abc"]

Output: "abc"

The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].
The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1].
The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1]. The odd array out is [1, 1], so we return the corresponding string, "abc".

Example 2

Input: words = ["aaa","bob","ccc","ddd"]

Output: "bob"

All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].

Constraints

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

Solution Approach

Compute difference arrays

Iterate through each string and calculate its difference array using alphabetical positions. This transforms the original string problem into a numerical pattern comparison problem, which fits the array scanning plus hash lookup pattern.

Use a hash map to track occurrences

Store each difference array as a key in a hash table and count its occurrences. The difference array that appears only once identifies the odd string efficiently, avoiding repeated full array comparisons.

Return the unique string

Once the unique difference array is found in the hash table, return the corresponding string from the original array. This ensures a clear mapping from the pattern back to the string, matching the exact pattern detection requirement.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * n) where m is the number of strings and n is their length, as each string is scanned once. Space complexity is O(m * n) due to storing difference arrays in the hash table for uniqueness detection.

What Interviewers Usually Probe

They may ask how to convert letters to numeric differences efficiently.
They may check if you can detect the single outlier using minimal comparisons.
They might probe alternative ways to store and compare difference arrays compactly.

Common Pitfalls or Variants

Common pitfalls

Forgetting that alphabet positions start at zero for 'a'.
Comparing strings directly instead of their difference arrays, missing the true pattern.
Using nested loops to compare every array pair, which is inefficient for larger inputs.

Follow-up variants

Strings of varying lengths where you must normalize or pad differences.
Finding multiple odd strings if more than one difference array occurs once.
Using modulo 26 differences for circular alphabet calculations.

FAQ

What is the main pattern used in Odd String Difference?

The problem uses array scanning plus hash lookup, converting strings to difference arrays and finding the unique one.

How do I calculate the difference array for a string?

Subtract the alphabet position of each character from the next one, forming an integer array of length n-1.

Can multiple strings be odd in the same input?

The standard problem assumes only one unique difference array; handling multiple outliers requires extending the hash count logic.

What is the time complexity of the solution?

It is O(m * n), where m is the number of strings and n is the length of each string.

Why is a hash table necessary in Odd String Difference?

The hash table efficiently counts occurrences of difference arrays, allowing quick identification of the unique string without repeated comparisons.

terminal

Solution

Solution 1: Hash Table Simulation

We use a hash table $d$ to maintain the mapping relationship between the difference array of the string and the string itself, where the difference array is an array composed of the differences of adjacent characters in the string. Since the problem guarantees that except for one string, the difference arrays of other strings are the same, we only need to find the string with a different difference array.

1

2

3

4

5

6

7

class Solution:
    def oddString(self, words: List[str]) -> str:
        d = defaultdict(list)
        for s in words:
            t = tuple(ord(b) - ord(a) for a, b in pairwise(s))
            d[t].append(s)
        return next(ss[0] for ss in d.values() if len(ss) == 1)

Solution 2

#### Rust

1

2

3

4

5

6

7

class Solution:
    def oddString(self, words: List[str]) -> str:
        d = defaultdict(list)
        for s in words:
            t = tuple(ord(b) - ord(a) for a, b in pairwise(s))
            d[t].append(s)
        return next(ss[0] for ss in d.values() if len(ss) == 1)

Continue Practicing