Abstract / Summary

Given two strings, find the difference between the count of characters at odd indices in each string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (70k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided oddString method receives a list of equal-length strings and returns the one whose pattern of consecutive character differences is unique among the list. The algorithm builds a fingerprint for each word, groups words by that fingerprint, and once enough information is gathered it identifies the group that contains a single entry - the odd string - and returns it immediately.

Building the fingerprint map

have = defaultdict(list)
for i, w in enumerate(words):
    difference = tuple([ ord(w[j]) - ord(w[j - 1]) for j in range(1, len(w)) ])
    have[difference].append(w)

In this block a defaultdict of lists named have is created. For each word w the code computes a tuple difference that captures the numeric distance between every pair of adjacent characters. The tuple is hashable, allowing it to serve directly as a dictionary key. Each word is appended to the list associated with its fingerprint, so have becomes a mapping from fingerprint to the collection of words that share it.

Early out detection

if len(have) >= 2 and i >= 2:
    for h in have:
        if len(have[h]) == 1:
            return have[h][0]

After processing at least three words (i >= 2) the algorithm checks whether at least two distinct fingerprints have been observed (len(have) >= 2). This condition guarantees that an outlier can be identified because there must be a majority fingerprint and a minority one. The inner loop scans the dictionary for a fingerprint whose list length is exactly one; the corresponding word is the odd string and is returned immediately, terminating the function without further iteration.

Edge-case handling

When a word consists of a single character, the list comprehension that builds difference yields an empty list, and tuple([]) produces an empty tuple. This empty tuple is a valid fingerprint, so single-character words are grouped correctly. The early-out guard (i >= 2) ensures that the function does not attempt to decide before three words have been examined, which would be insufficient to distinguish an outlier. The algorithm also works when the unique fingerprint appears at any position in the input list, because the scan for a singleton group occurs after each new word once the guard conditions are satisfied.

Performance-focused choices

Using ord on characters and storing the result of each subtraction in a tuple avoids repeated character-to-integer conversion during later lookups. The tuple’s immutability makes it an efficient dictionary key, enabling constant-time access to the associated list. The defaultdict eliminates the need for explicit existence checks before appending, reducing branching overhead. The early return after detecting a singleton group prevents unnecessary processing of the remaining words, which can be significant when the odd string appears early in a long list. Collectively, these decisions keep the runtime tight and the memory footprint modest, as only the fingerprints and the words themselves are retained.

Imagine you have a big box of secret word puzzles. Each word is made of letters, and each letter has a special secret number hidden inside it. To solve this puzzle, you look at how much the secret number changes as you move from one letter to the next.

Think of it like walking on a path where each step has a certain size. For most of the words in the box, the steps are exactly the same. You take a step, then another step, and they all follow a pattern. You can group these words together because their patterns match perfectly like pieces of a puzzle.

There is one word in the group that is different from all the others. Its steps are not the same size as the rest. The code goes through every word one by one and calculates the pattern of steps for each. It then sorts the words into different piles based on those patterns.

Once it has looked at enough words to see that some patterns match and others do not, it looks for the pile that only contains one single word. That lonely word is the one that does not fit with the others. Once it finds that special pile with only one item inside, it picks that word out to show which one is the odd one out.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java		C++		Python		TS
	WalkCCC	Java		C++		Python
	leetcode.ca	Java		C++	Go	Python	Rust	TS
	Progiez	Java		C++		Python
github	charles-wangkai	Java
	fsq			C++
	JoshCrozier		JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality