Odd String Difference
EasyPrompt
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 <= 100n == words[i].length2 <= n <= 20words[i]consists of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a list,
diffArrays, to store the computed difference array for each word. - Iterate through each
wordin the inputwordsarray.- For each
word, calculate its difference array by finding the difference in alphabet position between adjacent characters. - Add the resulting integer array to
diffArrays.
- For each
- After computing all difference arrays, use a nested loop to find the unique one.
- The outer loop iterates from
i = 0towords.length - 1. - The inner loop iterates from
j = 0towords.length - 1to count the frequency of the difference array at indexi. - To compare two difference arrays, a helper function or
Arrays.equalsis used.
- The outer loop iterates from
- 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.
Walkthrough
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.
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 }}Complexity
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`.
Trade-offs
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.
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.
Algorithm
- Initialize a
Map<List<Integer>, List<String>>to store mappings from a difference pattern to the words that have it. - Iterate through each
wordin thewordsarray.- 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-basedhashCodeandequalsmethods. - Add the current
wordto 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.
- For each
- 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.
Walkthrough
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.
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 }}Complexity
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.
Trade-offs
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.
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.
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])anddiff1 = getDiff(words[1]). - Compare
diff0anddiff1usingArrays.equals(). - Case 1:
diff0anddiff1are 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
diff0is the odd one; return it.
- Case 2:
diff0anddiff1are different.- This means one of
words[0]orwords[1]is the odd one out. - To find out which, calculate the difference array for the third word:
diff2 = getDiff(words[2]). - If
diff2is equal todiff0, thendiff0represents the common pattern, makingwords[1]the odd string. Returnwords[1]. - Otherwise,
diff1must be the common pattern, makingwords[0]the odd string. Returnwords[0].
- This means one of
Walkthrough
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:
-
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. -
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), thendiff0is the common pattern, andwords[1]must be the odd one out. Conversely, if the third array does not match the first, it must match the second (diff1), makingwords[0]the odd one out.
This method is highly efficient as it minimizes space usage to be constant relative to the number of words.
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 }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ""; }}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 ""; }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.