Odd string difference

Array Hash Table String

61.8% acceptance

Feb 25, 2026

432

123

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 differe nce[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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn odd_string(words: Vec<String>) -> String {
    fn diff(w: &str) -> Vec<i32> {
      let b: Vec<i32> = w.bytes().map(|x| x as i32).collect();
      b.windows(2).map(|p| p[1] - p[0]).collect()
    }
    let d0 = diff(&words[0]);
    let d1 = diff(&words[1]);
    if d0 != d1 {
      // one of word[0] or word[1] is odd - check with word[2]
      let d2 = diff(&words[2]);
      if d0 == d2 { return words[1].clone(); }
      return words[0].clone();
    }
    // d0 == d1, so find the word with different diff
    for w in &words[2..] {
      if diff(w) != d0 { return w.clone(); }
    }
    unreachable!()
  }
}