Skip to main content
Talentd

Odd String Difference - Solution & Explanation

EasyArrayHash TableString16 min readAsked at: IBM, Visa, Salesforce +1
Practice this problem

Problem Statement

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.

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.

This C code demonstrates a basic divide and conquer method where the input array is divided into two halves, solved individually, and then combined appropriately. The specific problem's logic should be implemented in the combine function.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), where n is the number of elements.
Space Complexity: O(log n) due to recursion stack space.

Try this approach in the editor →

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.

This C code implements a dynamic programming approach that uses an array to store subproblem solutions. Adjust combination logic within the loop to suit specific problem requirements.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), iterating only through each element.
Space Complexity: O(n), storing solutions for each subproblem.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Default Approach

Code

Rust

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Divide and Conquer with Recursive Method

Time Complexity: O(n log n), where n is the number of elements.
Space Complexity: O(log n) due to recursion stack space.

Approach 2: Dynamic Programming for Optimal Substructure

Time Complexity: O(n), iterating only through each element.
Space Complexity: O(n), storing solutions for each subproblem.

Hash Table Simulation—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Divide and Conquer with Recursive Pattern CheckO(n * m)O(m) to O(n * m)When exploring recursive strategies to isolate anomalies in grouped data
Dynamic Programming with Hash Map Pattern StorageO(n * m)O(n * m)General case; fastest and simplest method for detecting the unique difference pattern

Video Solution

2451. Odd String Difference | Leetcode BiWeekly 90 | LeetCode 2451 • Bro Coders • 1,650 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Odd String Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Rounds to Complete All Tasks