Problem Breakdown
We are given an array words containing strings composed of lowercase English letters. We need to find the length of the longest sequence (chain) where each word in the sequence is a “predecessor” of the next one. A predecessor relationship exists if adding exactly one character anywhere into the first string results in the second string. This implies two strict conditions:
- The successor must be exactly one character longer than its predecessor (
len(word2) == len(word1) + 1). - Removing any single character from
word2must result in a word that exists asword1.
Inputs: A list of strings words, length up to 1000, each string length up to 16.
Outputs: An integer representing the maximum chain length found.
Implicit Constraints & Edge Cases:
- Duplicates: The input may contain duplicate words (e.g.,
["a", "b", "ba"]vs["a", "a", "ba"]). Since a word cannot be its own predecessor, duplicates do not extend the chain length but must be handled to avoid redundant processing. We can treat unique words for DP state storage or process them sequentially (logic remains valid). - Single Word: If no two words satisfy the relationship, the answer is 1 (the longest possible chain containing just one word from the list).
- Empty Input: Constraints guarantee at least one word (
words.length >= 1), so we don’t need to handle an empty array.
Intuition
A brute-force approach would try every permutation of words or check all pairs for a predecessor relationship, which is where is the number of words and is max word length. While checking predecessors takes linear time with respect to string length (), doing this naively without ordering leads to redundant checks.
Key Insight: The predecessor must always be shorter than its successor by exactly one character. This suggests a Directed Acyclic Graph (DAG) structure where edges only go from shorter words to longer words. If we process the words in increasing order of length, when we are at word w, any potential predecessor for it must have already been processed and stored if it exists in our list.
Optimal Approach:
- Sort all unique words by their lengths (ascending). This ensures that when we evaluate a word, its possible predecessors (shorter strings) are available to us.
- Use Dynamic Programming with a Hash Map (
dp).dp[word]stores the length of the longest chain ending atword. - For each word in sorted order:
- Initialize
dp[current_word] = 1(the word itself forms a chain). - Generate all possible predecessors by removing one character from
current_word. - If any generated predecessor exists in our map, update the current word’s chain length using
max(dp[predecessor]) + 1.
- Initialize
- Track and return the maximum value found in the DP map.
Approach
- Preprocessing: Convert input to a set of unique words (optional but efficient) or sort the original list by string length. Sorting is crucial because we rely on shorter predecessors being processed first.
- DP Initialization: Create a dictionary
dpwhere keys are strings and values are integers representing chain lengths ending at that word. Initialize all entries to 1 implicitly as they start their own chains. - Iteration: Loop through the sorted words:
- For each character index in the current word, remove it temporarily to form a candidate predecessor string.
- Check if this candidate exists in
dp. If yes, updatecurrent_word’s chain length withmax(dp[candidate]) + 1.
- Result: The maximum value stored in
dpis the answer.
Complexity Analysis
- Time Complexity: where is number of words and is max word length (excluding sorting). Sorting takes . For each word, we generate at most predecessors. Hash map lookups are average . Total: . Given constraints (), this is highly efficient.
- Space Complexity: to store the words in the hash map and for sorting overhead (Python’s Timsort).
Edge Cases Handled
- No Valid Chains: If no word can extend another, every
dpentry remains 1; max is correctly returned as 1. - Duplicate Words: The logic handles duplicates naturally because the DP map stores one state per unique string content. Processing a duplicate later yields the same chain length (or less if it doesn’t find predecessors), which does not affect correctness of finding the longest. Using
setor dict keys ensures we don’t process identical strings redundantly for updates, though iterating duplicates is safe too. - Single Character Words: Removing a character from a 1-char word results in an empty string (not valid per constraints). The code checks existence of predecessors; if none exist, chain length remains 1.
Solution
class Solution:
def longestStrChain(self, words: List[str]) -> int:
# Sort by length to ensure we process shorter potential predecessors first
words.sort(key=len)
# dp stores the max chain length ending at a specific word string
dp = {}
for word in words:
current_len = 1
# Try removing each character to find valid predecessors
for i in range(len(word)):
predecessor = word[:i] + word[i+1:]
if predecessor in dp:
current_len = max(current_len, dp[predecessor] + 1)
dp[word] = current_len
return max(dp.values()) if dp else 0