LeetCode 2451 - Odd String Difference
The problem gives us an array of strings where every string has the same length. For each string, we construct a difference array by subtracting the alphabet position of consecutive characters.
Difficulty: 🟢 Easy
Topics: Array, Hash Table, String
Solution
LeetCode 2451 - Odd String Difference
Problem Understanding
The problem gives us an array of strings where every string has the same length. For each string, we construct a difference array by subtracting the alphabet position of consecutive characters.
For example, the string "adc" produces:
'd' - 'a' = 3'c' - 'd' = -1
So its difference array becomes [3, -1].
The important observation is that almost all strings share the exact same difference array. Only one string has a different pattern, and we must identify and return that string.
The input array words contains between 3 and 100 strings, and every string length is between 2 and 20. Since the input size is relatively small, we do not need extremely advanced optimizations. However, we still want a clean and efficient solution.
The expected output is the original string whose difference array differs from the majority.
A few important details matter here:
- Differences can be negative.
- Strings are guaranteed to contain only lowercase English letters.
- All strings have equal length, which means every difference array has the same size.
- Exactly one string is different, so there is always a unique answer.
An easy mistake is comparing strings directly instead of comparing their generated difference arrays. Another subtle issue is representing difference arrays consistently so they can be used as keys inside a hash map.
Approaches
Brute Force Approach
A straightforward solution is to generate the difference array for every string and compare each one against every other string.
For each string, we could count how many other strings share the same difference pattern. The one with frequency one would be the answer.
This approach works because the problem guarantees exactly one unique pattern. However, it performs many repeated comparisons. If there are m strings and each difference array has length n - 1, then comparing all pairs costs O(m^2 * n) time.
Although the constraints are small enough that this would still pass, it is unnecessarily inefficient.
Optimal Approach
A better approach is to use a hash map to count occurrences of each difference pattern.
We first convert every word into its difference array. Since lists cannot directly be dictionary keys in Python or map keys in Go, we convert the difference array into an immutable representation such as a tuple or formatted string.
As we process the words, we store:
- The difference pattern
- The number of times it appears
- The corresponding original word
At the end, the pattern with frequency one corresponds to the odd string.
This avoids repeated pairwise comparisons and processes every word only once.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(m² × n) | O(m × n) | Compares every difference array against all others |
| Optimal | O(m × n) | O(m × n) | Uses a hash map to count difference patterns |
Here, m is the number of words and n is the length of each word.
Algorithm Walkthrough
- Create a helper function that converts a word into its difference array.
For each adjacent pair of characters, subtract their alphabet positions. Store these differences in order because the sequence itself defines the pattern. 2. Initialize a hash map.
The key will be the difference pattern, and the value will store how many times that pattern appears. 3. Process each word one by one.
Generate its difference array and convert it into a hashable representation. 4. Update the frequency count for that pattern.
At the same time, store the original word associated with the pattern so we can return it later. 5. After processing all words, iterate through the stored patterns.
The pattern with frequency exactly one corresponds to the odd string. 6. Return the associated word.
Why it works
The problem guarantees that all strings except one share the same difference array. Therefore, when we count occurrences of each pattern, the common pattern appears multiple times while the unique pattern appears exactly once. Since every word is processed correctly and grouped by its difference pattern, the algorithm always identifies the odd string.
Python Solution
from collections import defaultdict
from typing import List, Tuple
class Solution:
def oddString(self, words: List[str]) -> str:
def build_difference(word: str) -> Tuple[int, ...]:
differences = []
for index in range(len(word) - 1):
difference = ord(word[index + 1]) - ord(word[index])
differences.append(difference)
return tuple(differences)
pattern_count = defaultdict(int)
pattern_word = {}
for word in words:
pattern = build_difference(word)
pattern_count[pattern] += 1
pattern_word[pattern] = word
for pattern, count in pattern_count.items():
if count == 1:
return pattern_word[pattern]
return ""
The solution starts by defining a helper function named build_difference. This function converts a word into its difference pattern by subtracting adjacent character codes.
The difference array is converted into a tuple because tuples are immutable and can be used as dictionary keys.
The pattern_count dictionary tracks how many times each pattern appears. The pattern_word dictionary stores the original word associated with each pattern.
As we iterate through the input words, we generate the corresponding pattern and update both dictionaries.
Finally, we scan through all patterns and return the word whose pattern appears exactly once.
The final return "" statement is technically unnecessary because the problem guarantees a valid answer, but it keeps the function syntactically complete.
Go Solution
package main
import (
"strconv"
"strings"
)
func buildDifference(word string) string {
var builder strings.Builder
for i := 0; i < len(word)-1; i++ {
diff := int(word[i+1]) - int(word[i])
builder.WriteString(strconv.Itoa(diff))
builder.WriteString(",")
}
return builder.String()
}
func oddString(words []string) string {
patternCount := make(map[string]int)
patternWord := make(map[string]string)
for _, word := range words {
pattern := buildDifference(word)
patternCount[pattern]++
patternWord[pattern] = word
}
for pattern, count := range patternCount {
if count == 1 {
return patternWord[pattern]
}
}
return ""
}
The Go solution follows the same overall logic as the Python version. Since Go slices cannot be used as map keys, the difference array is converted into a formatted string representation.
The strings.Builder type is used to efficiently build the pattern string. Each difference is separated by commas to avoid ambiguity between values.
Maps in Go naturally support frequency counting and pattern lookup.
There are no integer overflow concerns because character differences remain within a very small range from -25 to 25.
Worked Examples
Example 1
Input:
words = ["adc","wzy","abc"]
First, compute the difference arrays.
| Word | Calculation | Difference Array |
|---|---|---|
| "adc" | d-a=3, c-d=-1 | [3, -1] |
| "wzy" | z-w=3, y-z=-1 | [3, -1] |
| "abc" | b-a=1, c-b=1 | [1, 1] |
Now populate the hash map.
| Pattern | Count | Stored Word |
|---|---|---|
| (3, -1) | 2 | "wzy" |
| (1, 1) | 1 | "abc" |
The only pattern with count 1 is (1, 1).
Return:
"abc"
Example 2
Input:
words = ["aaa","bob","ccc","ddd"]
Compute the patterns.
| Word | Difference Array |
|---|---|
| "aaa" | [0, 0] |
| "bob" | [13, -13] |
| "ccc" | [0, 0] |
| "ddd" | [0, 0] |
Frequency table:
| Pattern | Count |
|---|---|
| (0, 0) | 3 |
| (13, -13) | 1 |
The unique pattern belongs to "bob".
Return:
"bob"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(m × n) | Each word and each character pair is processed once |
| Space | O(m × n) | Stores all generated difference patterns |
Here, m is the number of words and n is the word length.
Generating each difference array requires O(n) work, and we do this for all m words. The hash map stores one pattern per word in the worst case.
Test Cases
solution = Solution()
assert solution.oddString(["adc", "wzy", "abc"]) == "abc" # Provided example
assert solution.oddString(["aaa", "bob", "ccc", "ddd"]) == "bob" # Provided example
assert solution.oddString(["abc", "bcd", "xyz", "ace"]) == "ace" # Different positive gaps
assert solution.oddString(["aaa", "bbb", "ccc", "xyz"]) == "xyz" # Negative and positive mix
assert solution.oddString(["az", "by", "cx"]) == "az" # Two equal patterns, one different
assert solution.oddString(["ab", "bc", "cd", "xz"]) == "xz" # Minimum string length
assert solution.oddString(["mnop", "qrst", "uvwx", "abce"]) == "abce" # Larger strings
assert solution.oddString(["aaa", "aaa", "aba"]) == "aba" # Repeated identical words
assert solution.oddString(["abcd", "bcde", "cdef", "abcf"]) == "abcf" # Final difference differs
| Test | Why |
|---|---|
["adc","wzy","abc"] |
Validates the primary example |
["aaa","bob","ccc","ddd"] |
Validates mixed positive and negative differences |
["abc","bcd","xyz","ace"] |
Tests a clearly distinct pattern |
["aaa","bbb","ccc","xyz"] |
Ensures repeated identical patterns work |
["az","by","cx"] |
Tests very short words |
["ab","bc","cd","xz"] |
Validates minimum allowed word length |
["mnop","qrst","uvwx","abce"] |
Tests longer strings |
["aaa","aaa","aba"] |
Tests duplicate words |
["abcd","bcde","cdef","abcf"] |
Tests differences near the end of the word |
Edge Cases
One important edge case is when the string length is only two characters. In this situation, every difference array contains exactly one value. A careless implementation might incorrectly assume multiple differences exist. The current solution handles this naturally because the loop simply runs once.
Another important case is repeated identical words. For example, several copies of "aaa" all produce the same difference array [0, 0]. The hash map correctly aggregates these frequencies, ensuring the unique pattern still stands out.
Negative differences are also important. A string like "za" produces a difference of -25. If the implementation incorrectly assumes only positive values, the comparison logic would fail. Since the algorithm stores signed integer differences directly, both positive and negative values are handled correctly.
A final subtle edge case involves hash key representation. In Go, concatenating values without separators could produce ambiguous keys. For example, [1, 11] and [11, 1] could both become "111". The implementation avoids this by inserting commas between values when constructing the pattern string.