Longest String Chain: Hash Map DP Pattern

You are given a list of words. A word a is a predecessor of word b if you can insert exactly one letter into a at any position to get b. A word chain is a sequence of words where each word is a predecessor of the next. Find the length of the longest possible word chain.

This is LeetCode 1048: Longest String Chain, and it is a clean example of how hash map DP can replace the O(n^2) inner loop you see in classic Longest Increasing Subsequence style problems. Instead of comparing every pair of words, you use a hash map to look up predecessors directly.

Why this problem matters

Longest String Chain teaches you a pattern that shows up whenever the DP transition depends on a "reachable predecessor" rather than a simple numeric comparison. The key insight is that you can generate all possible predecessors of a word by removing one character at a time, then check whether that predecessor exists in a hash map. This turns an O(n^2) pairwise comparison into an O(n * L) scan, where L is the maximum word length.

This same "generate candidates, look them up in a map" technique applies to problems like Word Break (checking if substrings are in a dictionary) and graph problems where you build adjacency lists from transformation rules.

The approach

The strategy has three parts:

1. Sort words by length. A word can only be a predecessor of a longer word, so processing shorter words first guarantees that when you reach a word, all its potential predecessors have already been processed.

2. Use a hash map for DP. Store dp[word] = length of longest chain ending at word. For each word, generate every possible predecessor by removing one character at a time (there are len(word) candidates). If a candidate exists in the map, that is a valid predecessor.

3. Take the best predecessor. For each word, dp[word] = max(dp[predecessor] + 1) over all valid predecessors. The answer is the maximum value in the map.

This avoids the O(n^2) inner loop of comparing every pair. Generating predecessors costs O(L) per word, and each hash map lookup is O(L) for string hashing, giving O(n * L^2) total.

def longest_str_chain(words):
    words.sort(key=len)
    dp = {}

    for word in words:
        dp[word] = 1
        for i in range(len(word)):
            predecessor = word[:i] + word[i + 1:]
            if predecessor in dp:
                dp[word] = max(dp[word], dp[predecessor] + 1)

    return max(dp.values())

Let's walk through what this code does. First, it sorts the words by length so that every possible predecessor of a word is guaranteed to be processed before the word itself. Then, for each word, it initializes dp[word] = 1 because any single word is a chain of length 1. The inner loop tries removing each character at position i to form a candidate predecessor. If that predecessor already exists in the dp map, we can extend its chain. After processing all words, the answer is the maximum value stored in the map.

The predecessor generation is the clever part. Instead of checking whether word a can become word b by adding a letter (which would require trying 26 letters at every position), you flip the perspective: check whether word b can become word a by removing a letter. Removing one character from a word of length L gives you exactly L candidates, and each lookup in the hash map is fast.

Visual walkthrough

Let's trace through the example words = ["a", "b", "ba", "bca", "bda", "bdca"] step by step, watching how the dp map evolves as we process each word in order of length.

At the end, the maximum value in the dp map is 4, corresponding to the chain "a" to "ba" to "bca" to "bdca" (or equivalently "a" to "ba" to "bda" to "bdca"). Both chains have length 4.

Complexity analysis

Where n is the number of words and L is the maximum word length. The L^2 in the hash map approach comes from generating L predecessors per word, each of which involves creating a string of length up to L (string slicing). The space is O(n * L) because we store up to n words as keys in the map, each of length up to L.

Since the problem constrains L to at most 16 and n to at most 1000, the hash map DP runs comfortably within limits.

The building blocks

This problem is built on two reusable patterns.

The first is hash map DP with generated transitions. Instead of scanning all previous elements to find valid predecessors (as in the O(n^2) LIS approach), you generate the specific candidates you need and look them up in a map. This pattern appears in:

• Word Ladder (LeetCode 127): generate all one-letter transformations of a word, check which ones are in the dictionary. Same "generate candidates, look them up" idea, but used in BFS instead of DP.
• Word Break (LeetCode 139): at each position, check whether any dictionary word ends there. The dictionary acts as the hash map, and the substrings are the generated candidates.

The second building block is sort-then-DP on a natural ordering. By sorting words by length, you ensure that predecessors are always processed before their successors, which means a single left-to-right pass fills the DP table correctly. This is the same principle behind:

• Longest Increasing Subsequence (LeetCode 300): sort is implicit (process left to right in array order), and the DP scans backward for valid predecessors.
• Russian Doll Envelopes (LeetCode 354): sort by one dimension, then run LIS on the other dimension.

Edge cases to watch for

• Single word: the answer is 1. Every individual word is a chain of length 1.
• All words the same length: no word can be a predecessor of another (predecessor must be exactly one character shorter). Answer is 1.
• Words that differ by more than one character: even if word a is one character shorter than word b, a is only a predecessor if removing one character from b yields a. For example, "ab" is not a predecessor of "cd" even though their lengths differ by... well, they are the same length here. But "ab" is not a predecessor of "cde" either, because no single deletion from "cde" produces "ab".
• Duplicate words: the problem states all words are unique, so you do not need to handle duplicates. But if they appeared, the hash map approach would naturally collapse them.
• Long chains: the chain length is bounded by the range of word lengths present. If words span lengths 1 through 16, the maximum possible chain length is 16.

From understanding to recall

You have just seen how Longest String Chain combines sorting, hash map DP, and the "generate predecessors by deletion" trick into one clean solution. The pattern is not hard to understand when you read through it. But reproducing it under interview conditions, from a blank editor, is a different skill.

The gap between understanding and recall is where most people get stuck. You read the solution, nod along, and then two weeks later you are staring at a similar problem with no idea how to start. Spaced repetition closes that gap. You practice writing the solution from scratch at increasing intervals, and after a few reps the hash map DP pattern becomes automatic.

Longest String Chain is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems.

Related posts

• Longest Increasing Subsequence - The classic DP problem that Longest String Chain generalizes, with an O(n^2) scan-back inner loop
• Word Break - Another hash map DP problem where you check generated substrings against a dictionary
• Longest Common Subsequence - A 2D string DP problem that builds on similar subsequence intuition

Mastering these patterns individually gives you the building blocks to solve new problems on sight, without memorizing hundreds of solutions.