Domain 2MediumMEDIUM

Longest String Chain

LeetCode problem 1048: Longest String Chain (medium).

Domain: medium•Updated: 2026-09-07
#Hash Table#Dynamic Programming

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:

  1. The successor must be exactly one character longer than its predecessor (len(word2) == len(word1) + 1).
  2. Removing any single character from word2 must result in a word that exists as word1.

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 O(N2⋅L)O(N^2 \cdot L) where NN is the number of words and LL is max word length. While checking predecessors takes linear time with respect to string length (LL), 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:

  1. 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.
  2. Use Dynamic Programming with a Hash Map (dp). dp[word] stores the length of the longest chain ending at word.
  3. 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.
  4. Track and return the maximum value found in the DP map.

Approach

  1. 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.
  2. DP Initialization: Create a dictionary dp where 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.
  3. 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, update current_word’s chain length with max(dp[candidate]) + 1.
  4. Result: The maximum value stored in dp is the answer.

Complexity Analysis

  • Time Complexity: O(N⋅L)O(N \cdot L) where NN is number of words and LL is max word length (excluding sorting). Sorting takes O(Nlog⁡N)O(N \log N). For each word, we generate at most LL predecessors. Hash map lookups are average O(1)O(1). Total: O(N⋅L+Nlog⁡N)O(N \cdot L + N \log N). Given constraints (N=1000,L=16N=1000, L=16), this is highly efficient.
  • Space Complexity: O(N⋅L)O(N \cdot L) 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 dp entry 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 set or 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