# Odd String Difference
**Difficulty:** EASY
[External](https://leetcode.com/problems/odd-string-difference)
Canonical: https://scaleengineer.com/dsa/problems/odd-string-difference
**Data structures:** Array, Hash Table, String
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Visa](https://scaleengineer.com/companies/visa), [Datadog](https://scaleengineer.com/companies/datadog)
---
## 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 in_ `words` _that has different **difference integer array**._

**Example 1:**

**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:**

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

# Approaches
## Brute-Force with Pre-computation
This approach involves two main phases. First, we pre-compute the difference integer array for every string in the input array and store them. Second, we iterate through these computed difference arrays using a nested loop to find the one that is unique by counting its frequency.
**Time:** O(m^2 * n), where `m` is the number of words and `n` is the length of each word. Computing all difference arrays takes `O(m * n)`. The nested loop runs `m*m` times, and each comparison of arrays takes `O(n)` time, resulting in a dominant complexity of `O(m^2 * n)`. · **Space:** O(m * n), where `m` is the number of words and `n` is the length of each word. This is because we store `m` difference arrays, each of size `n-1`.
**Pros:** The logic is straightforward and relatively easy to implement.
**Cons:** The time complexity of O(m^2 * n) is inefficient and may be too slow for larger constraints.; Requires O(m * n) space to store all the difference arrays, which can be memory-intensive.
### Explanation
We begin by creating a list to hold the difference arrays for all words. We iterate through each `word` in the input `words` array. For each `word`, we calculate its difference array by iterating from the first character to the second-to-last and finding the difference in alphabet position between the current character and the next. This new difference array is then stored in our list.

Once all difference arrays are computed and stored, we proceed to find the unique one. This is accomplished with a nested loop. The outer loop selects a difference array, and the inner loop compares it against all other arrays in the list to count its occurrences. If the count for a particular difference array is exactly 1, we have found the odd one out. We then return the original string from the `words` array that corresponds to this unique difference array.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public String oddString(String[] words) {
        int n = words[0].length();
        List<int[]> diffArrays = new ArrayList<>();

        // 1. Pre-compute all difference arrays
        for (String word : words) {
            int[] diff = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                diff[i] = word.charAt(i + 1) - word.charAt(i);
            }
            diffArrays.add(diff);
        }

        // 2. Find the unique difference array using nested loops
        for (int i = 0; i < diffArrays.size(); i++) {
            int count = 0;
            for (int j = 0; j < diffArrays.size(); j++) {
                if (Arrays.equals(diffArrays.get(i), diffArrays.get(j))) {
                    count++;
                }
            }
            if (count == 1) {
                return words[i];
            }
        }
        return ""; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
- Create a list, `diffArrays`, to store the computed difference array for each word.
- Iterate through each `word` in the input `words` array.
  - For each `word`, calculate its difference array by finding the difference in alphabet position between adjacent characters.
  - Add the resulting integer array to `diffArrays`.
- After computing all difference arrays, use a nested loop to find the unique one.
  - The outer loop iterates from `i = 0` to `words.length - 1`.
  - The inner loop iterates from `j = 0` to `words.length - 1` to count the frequency of the difference array at index `i`.
  - To compare two difference arrays, a helper function or `Arrays.equals` is used.
- If the frequency count for a difference array is 1, it is the unique one. Return the original string `words[i]` that corresponds to it.

## Using a Hash Map for Frequency Counting
A more efficient approach uses a hash map to count the occurrences of each unique difference pattern. By grouping words by their difference arrays, we can find the unique one in linear time with respect to the total number of characters, avoiding the quadratic complexity of the brute-force method.
**Time:** O(m * n), where `m` is the number of words and `n` is the length of each word. For each of the `m` words, we compute the difference array (`O(n)`) and perform a map operation. The map key (a list of size `n`) takes `O(n)` to hash and compare, leading to a total time of `m * O(n)`. · **Space:** O(m * n). The map stores all the words, which have a total of `m * n` characters. The keys also take space, but since there are only two distinct keys, their space `O(n)` is not dominant.
**Pros:** Significantly faster than the brute-force approach with a time complexity of O(m * n).; The logic is clean and leverages a standard data structure for counting/grouping.
**Cons:** Uses O(m * n) space to store all the words in the map's values, which can be substantial.
### Explanation
The core idea is to map each distinct difference array pattern to the word(s) that produce it. We iterate through the `words` array, and for each `word`, we compute its difference array. Since primitive arrays in Java are not suitable as hash map keys (as they are compared by reference, not by content), we convert the integer difference array into a more suitable, hashable type like a `List<Integer>`.

This `List<Integer>` serves as the key for our hash map. The value associated with each key is a list of strings that share this difference pattern. As we process each word, we calculate its difference pattern, convert it to a list key, and add the word to the corresponding list in the map.

After populating the map, we simply iterate through its entries. The problem guarantees that exactly one string is different, which means one entry in the map will have a list containing just one string. We find this entry and return that single string.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public String oddString(String[] words) {
        Map<List<Integer>, List<String>> map = new HashMap<>();
        int n = words[0].length();

        for (String word : words) {
            List<Integer> diff = new ArrayList<>();
            for (int i = 0; i < n - 1; i++) {
                diff.add(word.charAt(i + 1) - word.charAt(i));
            }
            map.computeIfAbsent(diff, k -> new ArrayList<>()).add(word);
        }

        for (List<String> group : map.values()) {
            if (group.size() == 1) {
                return group.get(0);
            }
        }
        return ""; // Should not be reached
    }
}
```
### Algorithm
- Initialize a `Map<List<Integer>, List<String>>` to store mappings from a difference pattern to the words that have it.
- Iterate through each `word` in the `words` array.
  - For each `word`, compute its integer difference array.
  - Convert the integer array to a `List<Integer>`. This list will serve as the key for the hash map, as lists have content-based `hashCode` and `equals` methods.
  - Add the current `word` to the list of strings associated with its difference pattern key in the map. `map.computeIfAbsent(key, k -> new ArrayList<>()).add(word)` is a concise way to do this.
- After populating the map, iterate through its entries (or just its values).
- The problem guarantees one odd string, so one entry in the map will have a value list of size 1.
- Find this entry and return the single string from its list.

## Optimized Comparison with Constant Space
This is the most efficient approach in terms of space. It leverages the problem's constraint that exactly one string is different. By comparing the difference patterns of just the first few strings, we can quickly identify the common pattern and then find the single string that deviates from it, all without needing extra space proportional to the input size.
**Time:** O(m * n), where `m` is the number of words and `n` is the length of each word. In the worst-case scenario (when the first two words have the common pattern), we iterate through all `m` words once. For each word, we compute a difference array, which takes `O(n)` time. · **Space:** O(n), where `n` is the length of the strings. We only need to store a few difference arrays at a time (at most 3), each of size `n-1`. The space usage does not grow with `m`, the number of words.
**Pros:** Optimal space complexity of O(n), as it does not depend on the number of words.; Time complexity is efficient (O(m * n)) and has low overhead compared to the hash map approach (no hashing, no list object creation).; Very fast in practice due to minimal memory operations.
**Cons:** The logic involves more conditional branching than the hash map approach, which can make it slightly more complex to reason about.
### Explanation
The logic of this approach hinges on the crucial fact that there are only two distinct difference patterns in the entire input array: a common pattern and an odd one. This allows us to solve the problem without storing all patterns or using a hash map.

We start by computing the difference arrays for the first two words, `words[0]` and `words[1]`. Then we compare them:

1.  **If the first two difference arrays are identical:** We've found the common pattern. The odd string must appear later in the array. We can then iterate from `words[2]` onwards, calculating the difference array for each subsequent word and returning the first one that does not match this common pattern.

2.  **If the first two difference arrays are different:** This implies that one of them belongs to the odd string, and the other is the common pattern. To determine which is which, we need a tie-breaker. We examine a third word, `words[2]`, and compute its difference array. If this third array matches the first one (`diff0`), then `diff0` is the common pattern, and `words[1]` must be the odd one out. Conversely, if the third array does not match the first, it must match the second (`diff1`), making `words[0]` the odd one out.

This method is highly efficient as it minimizes space usage to be constant relative to the number of words.

```java
import java.util.Arrays;

class Solution {
    private int[] getDiff(String s) {
        int[] diff = new int[s.length() - 1];
        for (int i = 0; i < s.length() - 1; i++) {
            diff[i] = s.charAt(i + 1) - s.charAt(i);
        }
        return diff;
    }

    public String oddString(String[] words) {
        int[] diff0 = getDiff(words[0]);
        int[] diff1 = getDiff(words[1]);

        if (Arrays.equals(diff0, diff1)) {
            // The common pattern is diff0. Find the one that doesn't match.
            for (int i = 2; i < words.length; i++) {
                if (!Arrays.equals(getDiff(words[i]), diff0)) {
                    return words[i];
                }
            }
        } else {
            // One of words[0] or words[1] is the odd one.
            // Check words[2] to find the common pattern.
            int[] diff2 = getDiff(words[2]);
            if (Arrays.equals(diff0, diff2)) {
                // diff0 is the common pattern, so words[1] is the odd one.
                return words[1];
            } else {
                // diff1 must be the common pattern, so words[0] is the odd one.
                return words[0];
            }
        }
        return ""; // Should not be reached
    }
}
```
### Algorithm
- Define a helper function `getDiff(String s)` that takes a string and returns its integer difference array.
- Calculate the difference arrays for the first two words: `diff0 = getDiff(words[0])` and `diff1 = getDiff(words[1])`.
- Compare `diff0` and `diff1` using `Arrays.equals()`.
- **Case 1: `diff0` and `diff1` are equal.**
  - This means their pattern is the common one.
  - Iterate through the rest of the words from index 2.
  - For each word, calculate its difference array and compare it to `diff0`.
  - The first word whose difference array does not match `diff0` is the odd one; return it.
- **Case 2: `diff0` and `diff1` are different.**
  - This means one of `words[0]` or `words[1]` is the odd one out.
  - To find out which, calculate the difference array for the third word: `diff2 = getDiff(words[2])`.
  - If `diff2` is equal to `diff0`, then `diff0` represents the common pattern, making `words[1]` the odd string. Return `words[1]`.
  - Otherwise, `diff1` must be the common pattern, making `words[0]` the odd string. Return `words[0]`.

# Solutions
### Java

```java
class Solution {
public
  String oddString(String[] words) {
    var d = new HashMap<String, List<String>>();
    for (var s : words) {
      int m = s.length();
      var cs = new char[m - 1];
      for (int i = 0; i < m - 1; ++i) {
        cs[i] = (char)(s.charAt(i + 1) - s.charAt(i));
      }
      var t = String.valueOf(cs);
      d.putIfAbsent(t, new ArrayList<>());
      d.get(t).add(s);
    }
    for (var ss : d.values()) {
      if (ss.size() == 1) {
        return ss.get(0);
      }
    }
    return "";
  }
}

```

### CPP

```cpp
class Solution {
public:
  string oddString(vector<string> &words) {
    unordered_map<string, vector<string>> cnt;
    for (auto &w : words) {
      string d;
      for (int i = 0; i < w.size() - 1; ++i) {
        d += (char)(w[i + 1] - w[i]);
        d += ',';
      }
      cnt[d].emplace_back(w);
    }
    for (auto &[_, v] : cnt) {
      if (v.size() == 1) {
        return v[0];
      }
    }
    return "";
  }
};

```

### Python

```python
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)

```