Odd String Difference — Solution in Python, Java & C++
Odd String Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Odd String Difference is an easy coding problem on arrays, strings and hash table, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array words of strings that all have the same length n.
The difference array of a string s is the array [s[1]-s[0], s[2]-s[1], …, s[n-1]-s[n-2]] of character-code differences.
All but one of the strings share the same difference array. Return the odd one out.
Example 1
Input: words = ["adc","wzy","abc"]
Output: abc
Explanation: "adc" and "wzy" both have difference array [3,-1]; "abc" has [1,1].
Example 2
Input: words = ["aaa","bob","ccc","ddd"]
Output: bob
Explanation: The others have [0,0]; "bob" has [13,-13].
Example 3
Input: words = ["abm","bcn","alk"]
Output: alk
Constraints
3 <= words.length <= 100n == words[i].length2 <= n <= 20words[i] consists of lowercase English letters.Exactly one string has a different difference array.
Hints for Odd String Difference
Hint 1
Encode each difference array as a hashable key — joining the numbers with a separator works.
Hint 2
Group the word indices by that key.
Hint 3
Exactly one group has size 1; the word in it is the answer.
How to solve Odd String Difference
Reduce each word to a canonical key — its difference array — then group. The problem guarantees a 1-and-the-rest split, so the singleton group holds the answer.
Approach
- For each word, build its difference array and turn it into a string key.
- Map each key to the list of word indices producing it.
- Find the key whose list has exactly one element and return that word.
Why it works
Two words share a difference array exactly when their keys match, so the grouping is by the equivalence the problem defines. With words.length >= 3 and exactly one odd string, precisely one group is a singleton.
Complexity
- Time —
O(total characters) - Space —
O(total characters)
Pitfalls
- Concatenating the differences without a separator collides —
[1,11]and[11,1]both become"111". - Differences can be negative, so the key must survive a minus sign.
- Comparing only the first two words to pick the "majority" pattern breaks when one of them is the odd string.
Reference solution
Python
from typing import List
def oddString(words: List[str]) -> str:
groups = {}
for i, w in enumerate(words):
key = ",".join(str(ord(w[j]) - ord(w[j - 1])) for j in range(1, len(w)))
groups.setdefault(key, []).append(i)
for key, idxs in groups.items():
if len(idxs) == 1:
return words[idxs[0]]
return ""Java
public static String oddString(String[] words) {
HashMap<String, ArrayList<Integer>> groups = new HashMap<>();
for (int i = 0; i < words.length; i++) {
StringBuilder sb = new StringBuilder();
String w = words[i];
for (int j = 1; j < w.length(); j++) {
if (j > 1) sb.append(',');
sb.append(w.charAt(j) - w.charAt(j - 1));
}
String k = sb.toString();
groups.computeIfAbsent(k, x -> new ArrayList<>()).add(i);
}
for (Map.Entry<String, ArrayList<Integer>> e : groups.entrySet()) {
if (e.getValue().size() == 1) return words[e.getValue().get(0)];
}
return "";
}C++
string oddString(vector<string>& words) {
unordered_map<string, vector<int>> groups;
for (int i = 0; i < (int) words.size(); i++) {
string k;
const string& w = words[i];
for (int j = 1; j < (int) w.size(); j++) {
if (j > 1) k += ',';
k += to_string((int) w[j] - (int) w[j - 1]);
}
groups[k].push_back(i);
}
for (auto& e : groups) {
if (e.second.size() == 1) return words[e.second[0]];
}
return "";
}JavaScript
var oddString = function(words) {
function keyOf(w) {
const d = [];
for (let i = 1; i < w.length; i++) d.push(w.charCodeAt(i) - w.charCodeAt(i - 1));
return d.join(",");
}
const groups = {};
for (let i = 0; i < words.length; i++) {
const k = keyOf(words[i]);
if (!groups[k]) groups[k] = [];
groups[k].push(i);
}
const keys = Object.keys(groups);
for (let i = 0; i < keys.length; i++) {
if (groups[keys[i]].length === 1) return words[groups[keys[i]][0]];
}
return "";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.