Odd String Difference solution and explanation
IBM
9 more videos on this problem
2451. Odd String Difference | Leetcode BiWeekly 90 | LeetCode 2451Bro Coders · 6:39 · 1K views
ODD STRING DIFFERENCE || leetcode contestPrasun kumar · 0:26 · 822 views
Odd String Difference - Leetcode Biweekly Contest 90Gopala Krishna Reddy Maguluri · 0:20 · 618 views
2451. Odd String Difference (Leetcode Easy)Programming Live with Larry · 4:00 · 579 views
Leetcode BiWeekly contest 90 - Easy - Odd String DifferencePrakhar Agrawal · 8:23 · 481 views
LeetCode 2451. Odd String DifferenceYuki Kitayama · 14:26 · 340 views
2451. Odd String Difference | Biweekly 90 LeetCode Contest | Easy | Map Solution | #leetcodecontestBig-O(1) 💻 · 5:47 · 277 views
Leetcode Biweekly Contest 90 | PROBLEM 2451 , 2452, 2453code Explainer · 13:15 · 234 views
LeetCode 2451 | Odd String Difference | Matrix | Debugger | JavaSleepy Cracker · 13:09 · 170 views
Leetcode 2451. Odd String DifferenceElite Code · 15:40 · 161 views
The 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 <= 100n == words[i].length2 <= n <= 20words[i]consists of lowercase English letters.
Approach overview
Problem Overview: You receive an array of equal‑length strings. For each word, compute the difference between adjacent characters (for example "abcd" → [1,1,1]). Most words share the same difference pattern, but one word has a different pattern. Return that odd string.
Approach 1: Divide and Conquer with Recursive Method (Time: O(n * m), Space: O(m) recursion + pattern storage)
This method recursively splits the array of words into halves and evaluates the difference pattern of representative strings from each segment. For each word, compute its difference array by iterating over characters and subtracting adjacent ASCII values. The recursion compares pattern groups from left and right halves to detect which side contains the outlier pattern. Once a mismatch is identified, the recursion continues only on that segment until the odd string is isolated. This approach demonstrates how divide‑and‑conquer can reduce comparisons when you only need to locate a single anomaly among otherwise identical patterns.
Approach 2: Dynamic Programming for Optimal Substructure (Time: O(n * m), Space: O(n * m))
A more direct solution builds a reusable representation of each word’s difference pattern. Iterate through the array once and compute a signature string such as "1#1#1" from adjacent character differences. Store these signatures in a hash map where the key is the pattern and the value is the list or count of words sharing it. Because almost all strings share the same pattern, the map quickly reveals the single pattern with frequency one. Dynamic programming ideas apply because each difference value is derived from previously processed characters and reused as part of the signature structure. Hash lookups run in constant time, making this solution straightforward and efficient for typical constraints.
Both approaches rely on iterating through characters and constructing a difference representation. Understanding how to derive these patterns from a string and efficiently group them with a hash table is the core skill. The input itself is processed sequentially as an array of words.
Recommended for interviews: The hash‑based pattern grouping approach (Approach 2). It’s concise, runs in linear time relative to the total characters processed (O(n * m)), and clearly shows your ability to transform strings into comparable signatures. Discussing the divide‑and‑conquer idea first can demonstrate problem‑solving depth, but interviewers usually expect the hash map solution.
Approach 1: Approach 1: Divide and Conquer with Recursive Method
This approach focuses on dividing the problem into smaller sub-problems (i.e., divide and conquer). We recursively solve each sub-problem, and combine their solutions to find the final solution. This technique is efficient for problems that can naturally be divided into similar sub-problems.
def divide_conquer(arr, low, high):
if low == high:
return arr[low]
mid = (low + high) // 2
left_result = divide_conquer(arr, low, mid)
right_result = divide_conquer(arr, mid + 1, high)
return combine(left_result, right_result)
def combine(left, right):
# Combine logic
pass
array = [Your array elements]
result = divide_conquer(array, 0, len(array) - 1)
print(result)public class DivideConquer {
public static int divideConquer(int[] arr, int low, int high) {
if (low == high)
return arr[low];
int mid = (low + high) / 2;
int leftResult = divideConquer(arr, low, mid);
int rightResult = divideConquer(arr, mid + 1, high);
return combine(leftResult, rightResult);
}
public static int combine(int left, int right) {
// Combine logic
return 0;
}
public static void main(String[] args) {
int[] arr = {Your array elements};
int result = divideConquer(arr, 0, arr.length - 1);
System.out.println(result);
}
}#include <iostream>
using namespace std;
int divideConquer(vector<int>& arr, int low, int high) {
if (low == high)
return arr[low];
int mid = (low + high) / 2;
int leftResult = divideConquer(arr, low, mid);
int rightResult = divideConquer(arr, mid + 1, high);
return combine(leftResult, rightResult);
}
int combine(int left, int right) {
// Combine logic
}
int main() {
vector<int> arr = {Your array elements};
int result = divideConquer(arr, 0, arr.size() - 1);
cout << result << endl;
return 0;
}function divideConquer(arr, low, high) {
if (low === high) return arr[low];
const mid = Math.floor((low + high) / 2);
const leftResult = divideConquer(arr, low, mid);
const rightResult = divideConquer(arr, mid + 1, high);
return combine(leftResult, rightResult);
}
function combine(left, right) {
// Combine logic
return 0;
}
const array = [Your array elements];
const result = divideConquer(array, 0, array.length - 1);
console.log(result);#include <stdio.h>
// Function to perform divide and conquer
int divideConquer(int arr[], int low, int high) {
if (low == high)
return arr[low];
int mid = (low + high) / 2;
int leftResult = divideConquer(arr, low, mid);
int rightResult = divideConquer(arr, mid+1, high);
return combine(leftResult, rightResult);
}
int combine(int left, int right) {
// Combine logic, depends on the problem
}
int main() {
int arr[] = {Your array elements};
int n = sizeof(arr)/sizeof(arr[0]);
int result = divideConquer(arr, 0, n-1);
printf("%d", result);
return 0;
}using System;
class Program {
static int DivideConquer(int[] arr, int low, int high) {
if (low == high)
return arr[low];
int mid = (low + high) / 2;
int leftResult = DivideConquer(arr, low, mid);
int rightResult = DivideConquer(arr, mid + 1, high);
return Combine(leftResult, rightResult);
}
static int Combine(int left, int right) {
// Combine logic
return 0;
}
static void Main() {
int[] arr = {Your array elements};
int result = DivideConquer(arr, 0, arr.Length - 1);
Console.WriteLine(result);
}
}This Python script uses a divide and conquer technique with recursion to solve the problem by breaking it into sub-problems and combining their solutions.
Time Complexity: O(n log n).
Space Complexity: O(log n) due to recursive calls.
Approach 2: Approach 2: Dynamic Programming for Optimal Substructure
This approach uses dynamic programming to take advantage of the optimal substructure property of the problem. By solving overlapping subproblems only once and storing their results, DP can optimize the solution process significantly.
def dynamic_programming(arr):
dp = [0] * len(arr)
dp[0] = arr[0]
for i in range(1, len(arr)):
dp[i] = dp[i-1] + arr[i]
return dp[-1]
array = [Your array elements]
result = dynamic_programming(array)
print(result)public class DynamicProgrammingSolution {
public static int dynamicProgramming(int[] arr) {
int[] dp = new int[arr.length];
dp[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
dp[i] = arr[i] + dp[i - 1];
}
return dp[arr.length - 1];
}
public static void main(String[] args) {
int[] arr = {Your array elements};
int result = dynamicProgramming(arr);
System.out.println(result);
}
}#include <iostream>
#include <vector>
using namespace std;
int dynamicProgramming(vector<int>& arr) {
vector<int> dp(arr.size());
dp[0] = arr[0];
for (size_t i = 1; i < arr.size(); ++i) {
dp[i] = arr[i] + dp[i-1];
}
return dp.back();
}
int main() {
vector<int> arr = {Your array elements};
int result = dynamicProgramming(arr);
cout << result << endl;
return 0;
}function dynamicProgramming(arr) {
const dp = [arr[0]];
for (let i = 1; i < arr.length; i++) {
dp[i] = arr[i] + dp[i - 1];
}
return dp[dp.length - 1];
}
const array = [Your array elements];
const result = dynamicProgramming(array);
console.log(result);#include <stdio.h>
// Function to perform dynamic programming
int dynamicProgramming(int arr[], int n) {
int dp[n];
// Base case setup
dp[0] = arr[0]; // Initialize with initial value
for (int i = 1; i < n; i++) {
dp[i] = arr[i] + dp[i-1]; // Example logic
}
return dp[n-1];
}
int main() {
int arr[] = {Your array elements};
int n = sizeof(arr)/sizeof(arr[0]);
int result = dynamicProgramming(arr, n);
printf("%d", result);
return 0;
}using System;
class Program {
static int DynamicProgramming(int[] arr) {
int[] dp = new int[arr.Length];
dp[0] = arr[0];
for (int i = 1; i < arr.Length; i++) {
dp[i] = arr[i] + dp[i - 1];
}
return dp[arr.Length - 1];
}
static void Main() {
int[] arr = {Your array elements};
int result = DynamicProgramming(arr);
Console.WriteLine(result);
}
}Python code leveraging dynamic programming to compute the result by using a DP list that captures the solution space efficiently. Tailor the loop logic to fit the problem.
Time Complexity: O(n).
Space Complexity: O(n), owing to the DP list used for storage.
Approach 3: Hash Table Simulation
We use a hash table d to maintain the mapping relationship between the difference array of the string and the string itself, where the difference array is an array composed of the differences of adjacent characters in the string. Since the problem guarantees that except for one string, the difference arrays of other strings are the same, we only need to find the string with a different difference array.
The time complexity is O(m times n), and the space complexity is O(m + n). Here, m and n are the length of the string and the number of strings, respectively.
function oddString(words: string[]): string {
const d: Map<string, string[]> = new Map();
for (const s of words) {
const cs: number[] = [];
for (let i = 0; i < s.length - 1; ++i) {
cs.push(s[i + 1].charCodeAt(0) - s[i].charCodeAt(0));
}
const t = cs.join(',');
if (!d.has(t)) {
d.set(t, []);
}
d.get(t)!.push(s);
}
for (const [_, ss] of d) {
if (ss.length === 1) {
return ss[0];
}
}
return '';
}func oddString(words []string) string {
d := map[string][]string{}
for _, s := range words {
m := len(s)
cs := make([]byte, m-1)
for i := 0; i < m-1; i++ {
cs[i] = s[i+1] - s[i]
}
t := string(cs)
d[t] = append(d[t], s)
}
for _, ss := range d {
if len(ss) == 1 {
return ss[0]
}
}
return ""
}use std::collections::HashMap;
impl Solution {
pub fn odd_string(words: Vec<String>) -> String {
let n = words[0].len();
let mut map: HashMap<String, (bool, usize)> = HashMap::new();
for (i, word) in words.iter().enumerate() {
let mut k = String::new();
for j in 1..n {
k.push_str(&(word.as_bytes()[j] - word.as_bytes()[j - 1]).to_string());
k.push(',');
}
let new_is_only = !map.contains_key(&k);
map.insert(k, (new_is_only, i));
}
for (is_only, i) in map.values() {
if *is_only {
return words[*i].clone();
}
}
String::new()
}
}Approach 4: Default Approach
use std::collections::HashMap;
impl Solution {
pub fn odd_string(words: Vec<String>) -> String {
let mut h = HashMap::new();
for w in words {
let bytes: Vec<i32> = w
.bytes()
.zip(w.bytes().skip(1))
.map(|(current, next)| (next - current) as i32)
.collect();
let s: String = bytes.iter().map(|&b| char::from(b as u8)).collect();
h.entry(s).or_insert(vec![]).push(w);
}
for strs in h.values() {
if strs.len() == 1 {
return strs[0].clone();
}
}
String::from("")
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Divide and Conquer with Recursive Method | Time Complexity: O(n log n). |
| Approach 2: Dynamic Programming for Optimal Substructure | Time Complexity: O(n). |
| Hash Table Simulation | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer with Recursive Pattern Check | O(n * m) | O(m) to O(n * m) | When exploring recursive strategies to isolate anomalies in grouped data |
| Dynamic Programming with Hash Map Pattern Storage | O(n * m) | O(n * m) | General case; fastest and simplest method for detecting the unique difference pattern |
Frequently asked questions
Is Odd String Difference easy or hard?
Odd String Difference is classified as an Easy problem. The main challenge is recognizing that adjacent character differences form a unique pattern for each string. Once you convert words into these signatures, the problem reduces to simple hash map grouping.
Odd String Difference Python/Java solution
In Python or Java, iterate through each word and build a string representing the differences between adjacent characters. Use a dictionary (Python) or HashMap (Java) to count occurrences of each pattern. The word whose pattern appears exactly once is returned as the answer.
How to solve Odd String Difference in O(n)?
Treat m (the word length) as a small constant and process each word once. For every string, compute its adjacent character differences and convert them into a signature key. Insert the key into a hash map and track counts. The signature with frequency one corresponds to the odd string.
What is the best approach for Odd String Difference?
The best approach computes a difference signature for each word and stores it in a hash map. Each signature represents the difference between adjacent characters. Because all but one string share the same pattern, the map quickly identifies the pattern with frequency one. This runs in O(n * m) time where n is the number of words and m is the word length.
Is Odd String Difference asked at Google/Amazon/Meta?
Problems involving string pattern transformation and hash grouping are common in interviews at companies like Google, Amazon, and Meta. While this exact question may not always appear, the technique of converting strings into comparable signatures using hash maps is frequently tested.
What data structure is used in Odd String Difference?
The main data structure is a hash table (hash map). It stores the computed difference pattern as a key and the corresponding words or counts as values. Arrays or lists are also used to iterate through characters and compute adjacent ASCII differences.
What is the time complexity of Odd String Difference?
The typical optimal solution runs in O(n * m) time. Each of the n strings requires iterating through its m characters to compute adjacent differences. Hash map insertion and lookup are constant on average, so the total complexity scales with the number of processed characters.