Removing a character from a word so that the resulting string is still a valid dictionary word is a classic problem in algorithm design. It appears in spell checkers, word games, and computational linguistics research. This article presents a clean algorithm for solving this problem, walks through implementations in Python and JavaScript, and analyzes the time and space complexity.

Problem Definition

Given a word and a set of valid dictionary words, find all positions where removing a single character produces a word that exists in the dictionary. For example, given the word "brand" and a dictionary containing "band", "bran", and "brad", removing the 'r' at index 1 yields "band", removing the 'd' at index 4 yields "bran", and removing the 'n' at index 3 yields "brad".

Algorithm Design

The approach is straightforward. For a word of length n, there are exactly n possible single-character removals. Generate each candidate by skipping one character at a time, then check whether the candidate exists in the dictionary. Using a hash set for the dictionary makes each lookup O(1) on average.

Steps:

1. Load the dictionary into a hash set for constant-time lookups.
2. Iterate through each index i from 0 to n-1.
3. Build the candidate word by concatenating the substring before index i with the substring after index i.
4. If the candidate exists in the dictionary set, record it as a valid result.

Python Implementation

1def find_reducible_words(word, dictionary):
2    dict_set = set(dictionary)
3    results = []
4
5    for i in range(len(word)):
6        candidate = word[:i] + word[i + 1:]
7        if candidate in dict_set:
8            results.append((i, candidate))
9
10    return results
11
12
13# Example usage
14dictionary = ["band", "bran", "brad", "ban", "cat", "car"]
15word = "brand"
16matches = find_reducible_words(word, dictionary)
17
18for index, reduced in matches:
19    print(f"Remove '{word[index]}' at index {index} -> '{reduced}'")

Output:

Remove 'r' at index 1 -> 'band'
Remove 'n' at index 3 -> 'brad'
Remove 'd' at index 4 -> 'bran'

JavaScript Implementation

1function findReducibleWords(word, dictionary) {
2  const dictSet = new Set(dictionary);
3  const results = [];
4
5  for (let i = 0; i < word.length; i++) {
6    const candidate = word.slice(0, i) + word.slice(i + 1);
7    if (dictSet.has(candidate)) {
8      results.push({ index: i, removed: word[i], result: candidate });
9    }
10  }
11
12  return results;
13}
14
15const dictionary = ["band", "bran", "brad", "ban", "cat", "car"];
16const word = "brand";
17const matches = findReducibleWords(word, dictionary);
18
19matches.forEach(m => {
20  console.log(`Remove '${m.removed}' at index ${m.index} -> '${m.result}'`);
21});

Recursive Word Reduction Chain

A more interesting variant asks: what is the longest chain of single-character removals where every intermediate word is valid? For example, "starting" could reduce to "staring", then "string", then "sting", then "sing", then "sin", then "in", then "I". This is solvable with depth-first search and memoization.

1def longest_reduction_chain(word, dict_set, memo=None):
2    if memo is None:
3        memo = {}
4    if word in memo:
5        return memo[word]
6    if word not in dict_set:
7        return []
8
9    best_chain = [word]
10
11    for i in range(len(word)):
12        candidate = word[:i] + word[i + 1:]
13        if candidate in dict_set:
14            sub_chain = longest_reduction_chain(candidate, dict_set, memo)
15            if len(sub_chain) + 1 > len(best_chain):
16                best_chain = [word] + sub_chain
17
18    memo[word] = best_chain
19    return best_chain
20
21
22dictionary = {"starting", "staring", "string", "sting", "sing", "sin", "in", "i",
23              "star", "tar", "ar", "a"}
24chain = longest_reduction_chain("starting", dictionary)
25print(" -> ".join(chain))

Complexity Analysis

For the basic single-removal algorithm:

• Time complexity: O(n * k) where n is the word length and k is the cost of building each candidate string. Since string slicing creates a new string of length n-1, the total work is O(n^2). Dictionary lookups are O(1) amortized with a hash set.
• Space complexity: O(m) where m is the dictionary size, for storing the hash set. The results list uses O(n) space in the worst case.

For the recursive chain variant, the time complexity depends on how many valid intermediate words exist. With memoization, each word is computed at most once, so the total work is bounded by O(m * n^2) where m is the number of reachable dictionary words and n is the maximum word length.

Common Pitfalls

Case sensitivity can silently break lookups. If the dictionary contains "Band" but the candidate generates "band", the lookup will fail. Normalize all words to lowercase before processing.

Another issue is handling duplicate results. If a word has repeated characters (like "book"), removing either 'o' produces the same candidate "bok". Depending on your requirements, you may want to deduplicate using a set.

Performance degrades if the dictionary is stored as a list instead of a set. A list lookup is O(m) per query, turning the overall complexity from O(n^2) to O(n * m), which becomes impractical for large dictionaries with hundreds of thousands of entries.

Summary

The word reduction algorithm generates all possible single-character deletions and checks each against a dictionary stored in a hash set. The basic version runs in O(n^2) time and is simple to implement in any language. The recursive chain variant uses DFS with memoization to find the longest sequence of valid reductions. Always use a hash set for the dictionary, normalize case, and handle duplicate candidates to avoid subtle bugs.