Odd String Difference

Easy
537.

Odd String Difference

Odd String Difference is an easy coding problem on arrays, strings and hash table, asked in Amazon and Adobe interviews.

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 <= 100
  • n == words[i].length
  • 2 <= n <= 20
  • words[i] consists of lowercase English letters.
  • Exactly one string has a different difference array.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {string}
 */
var oddString = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • n == words[i].length
  • 2 <= n <= 20
  • words[i] consists of lowercase English letters.
  • Exactly one string has a different difference array.

Hints for Odd String Difference

  1. Hint 1

    Encode each difference array as a hashable key — joining the numbers with a separator works.

  2. Hint 2

    Group the word indices by that key.

  3. 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

  1. For each word, build its difference array and turn it into a string key.
  2. Map each key to the list of word indices producing it.
  3. 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings