Problem

You are given an array of equal-length strings words. Assume that the length of each string is n.

Each string words[i] can be converted into a difference integer array difference[i] of length n - 1 where difference[i][j] = words[i][j+1] -words[i][j] where 0 <= j <= n - 2. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a' is 0, 'b' is 1, and 'z' is 25.

  • For example, for the string "acb", the difference integer array is [2 - 0, 1 - 2] = [2, -1].

All the strings in words have the same difference integer array, except one. You should find that string.

Return the string inwords that has differentdifference integer array.

Examples

Example 1

1
2
3
4
5
6
7

Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation: 
- 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

1
2
3

Input: words = ["aaa","bob","ccc","ddd"]
Output: "bob"
Explanation: 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

Method 1 – Hash Map and Frequency

Intuition

Each string can be represented by its difference array. All but one string share the same difference array. By counting the frequency of each difference array, we can find the unique one and return its corresponding string.

Approach

  1. For each word, compute its difference array as a tuple.
  2. Use a hash map to count the frequency of each difference array.
  3. Find the difference array that occurs only once.
  4. Return the string corresponding to that unique difference array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    string oddString(vector<string>& words) {
        unordered_map<string, int> freq;
        vector<string> diff_strs;
        for (auto& w : words) {
            string d;
            for (int i = 1; i < w.size(); ++i) {
                d += to_string(w[i] - w[i-1]) + ",";
            }
            diff_strs.push_back(d);
            freq[d]++;
        }
        string odd;
        for (int i = 0; i < diff_strs.size(); ++i) {
            if (freq[diff_strs[i]] == 1) return words[i];
        }
        return "";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func oddString(words []string) string {
    freq := map[string]int{}
    diffStrs := make([]string, len(words))
    for i, w := range words {
        d := ""
        for j := 1; j < len(w); j++ {
            d += fmt.Sprintf("%d,", int(w[j])-int(w[j-1]))
        }
        diffStrs[i] = d
        freq[d]++
    }
    for i, d := range diffStrs {
        if freq[d] == 1 {
            return words[i]
        }
    }
    return ""
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public String oddString(String[] words) {
        Map<String, Integer> freq = new HashMap<>();
        String[] diffStrs = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            StringBuilder d = new StringBuilder();
            for (int j = 1; j < words[i].length(); j++) {
                d.append((words[i].charAt(j) - words[i].charAt(j-1)) + ",");
            }
            diffStrs[i] = d.toString();
            freq.put(diffStrs[i], freq.getOrDefault(diffStrs[i], 0) + 1);
        }
        for (int i = 0; i < diffStrs.length; i++) {
            if (freq.get(diffStrs[i]) == 1) return words[i];
        }
        return "";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun oddString(words: Array<String>): String {
        val freq = mutableMapOf<String, Int>()
        val diffStrs = Array(words.size) { "" }
        for (i in words.indices) {
            val d = buildString {
                for (j in 1 until words[i].length) {
                    append(words[i][j] - words[i][j-1]).append(",")
                }
            }
            diffStrs[i] = d
            freq[d] = freq.getOrDefault(d, 0) + 1
        }
        for (i in diffStrs.indices) {
            if (freq[diffStrs[i]] == 1) return words[i]
        }
        return ""
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def oddString(self, words: list[str]) -> str:
        from collections import Counter
        diffs = [tuple(ord(w[i+1]) - ord(w[i]) for i in range(len(w)-1)) for w in words]
        cnt = Counter(diffs)
        for i, d in enumerate(diffs):
            if cnt[d] == 1:
                return words[i]
        return ""
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn odd_string(words: Vec<String>) -> String {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        let mut diff_vecs = Vec::new();
        for w in &words {
            let d: Vec<i32> = w.chars().zip(w.chars().skip(1)).map(|(a, b)| b as i32 - a as i32).collect();
            freq.entry(d.clone()).and_modify(|x| *x += 1).or_insert(1);
            diff_vecs.push(d);
        }
        for (i, d) in diff_vecs.iter().enumerate() {
            if freq[d] == 1 {
                return words[i].clone();
            }
        }
        "".to_string()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    oddString(words: string[]): string {
        const diffs: string[] = words.map(w => {
            let d = []
            for (let i = 1; i < w.length; i++) d.push(w.charCodeAt(i) - w.charCodeAt(i-1))
            return d.join(',')
        })
        const freq = new Map<string, number>()
        for (let d of diffs) freq.set(d, (freq.get(d) ?? 0) + 1)
        for (let i = 0; i < diffs.length; i++) {
            if (freq.get(diffs[i]) === 1) return words[i]
        }
        return ""
    }
}

Complexity

  • ⏰ Time complexity: O(m * n), where m is the number of words and n is the length of each word. We compute differences for each word.
  • 🧺 Space complexity: O(m * n), for storing difference arrays and frequency map.