Skip to content

2451. Odd String Difference

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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 pairs of 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 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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 pairs of word and its corresponding hash code.
  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 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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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