2451. Odd String Difference LeetCode Solution

In this guide, you will get 2451. Odd String Difference LeetCode Solution with the best time and space complexity. The solution to Odd String Difference problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Odd String Difference solution in C++
Odd String Difference solution in Java
Odd String Difference solution in Python
Additional Resources

2451. Odd String Difference LeetCode Solution image

Problem Statement of Odd String Difference

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2451. Odd String Difference LeetCode Solution in C++

class Solution {
 public:
  string oddString(vector<string>& words) {
    const vector<pair<string, string>> wordAndDiffStrs =
        getWordAndDiffStrs(words);
    unordered_map<string, int> diffStrCount;

    for (const auto& [_, diffStr] : wordAndDiffStrs)
      ++diffStrCount[diffStr];

    for (const auto& [word, diffStr] : wordAndDiffStrs)
      if (diffStrCount[diffStr] == 1)
        return word;

    throw;
  }

 private:
  // Returns the pairs of the word and its corresponding difference string.
  // e.g. [("adc", "3#-1#"), ("wzy", "3#-1#"), ("abc", "1#1#")]
  vector<pair<string, string>> getWordAndDiffStrs(const vector<string>& words) {
    vector<pair<string, string>> wordAndDiffStrs;
    for (const string& word : words)
      wordAndDiffStrs.emplace_back(word, getDiffStr(word));
    return wordAndDiffStrs;
  }

  // Returns the difference string of `s`.
  // e.g. getDiffStr("adc") -> "3#-1#"
  string getDiffStr(const string& s) {
    string diffStr;
    for (int i = 1; i < s.length(); ++i)
      diffStr += to_string(s[i] - s[i - 1]) + "#";
    return diffStr;
  }
};
/* code provided by PROGIEZ */

2451. Odd String Difference LeetCode Solution in Java

class Solution {
  public String oddString(String[] words) {
    List<Pair<String, Integer>> wordAndHashCodes = getWordAndHashCodes(words);
    Map<Integer, Integer> hashCodeCount = new HashMap<>();

    for (Pair<String, Integer> wordAndHashCode : wordAndHashCodes)
      hashCodeCount.merge(wordAndHashCode.getValue(), 1, Integer::sum);

    for (Pair<String, Integer> wordAndHashCode : wordAndHashCodes)
      if (hashCodeCount.get(wordAndHashCode.getValue()) == 1)
        return wordAndHashCode.getKey();

    throw new IllegalArgumentException();
  }

  // Returns the pairs of the word and its corresponding difference string.
  // e.g. [("adc", "3#-1#"), ("wzy", "3#-1#"), ("abc", "1#1#")]
  private List<Pair<String, Integer>> getWordAndHashCodes(String[] words) {
    List<Pair<String, Integer>> wordAndHashCodes = new ArrayList<>();
    for (final String word : words)
      wordAndHashCodes.add(new Pair<>(word, getDiffStr(word).hashCode()));
    return wordAndHashCodes;
  }

  // Returns the difference string of `s`.
  // e.g. getDiffStr("adc") -> "3#-1#"
  private String getDiffStr(final String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i < s.length(); ++i)
      sb.append(s.charAt(i) - s.charAt(i - 1)).append("#");
    return sb.toString();
  }
}
// code provided by PROGIEZ

2451. Odd String Difference LeetCode Solution in Python

class Solution:
  def oddString(self, words: list[str]) -> str:
    def getDiff(s: str) -> list[int]:
      return [ord(b) - ord(a) for a, b in zip(s, s[1:])]

    wordAndDiffTuples = [(word, tuple(getDiff(word))) for word in words]
    diffTupleCount = collections.Counter()

    for _, diffTuple in wordAndDiffTuples:
      diffTupleCount[diffTuple] += 1

    for word, diffTuple in wordAndDiffTuples:
      if diffTupleCount[diffTuple] == 1:
        return word
 # code by PROGIEZ