Bottom-Up Dynamic Programming.

Sorting: By sorting words by length, we satisfy the topological order requirement. We never need to look "forward" in the list, only backward at shorter words we've already processed.

Generation vs. Comparison: instead of comparing every word against every other word (O(N^2)), we take a word and generate all possible predecessors by removing one character.

Since the maximum length (L) is only 16, generating predecessors is extremely fast.

In Longest String Chain, you are given a simple list of words (e.g., ["a", "b", "ba", "bca", "bda", "bdca"]). It looks like an array problem, not a graph problem. You have to realize that words are nodes and a "predecessor" relationship (deleting one character) defines the edges.

"How to extend this to a big-data situation?"

This is a standard Google transition. They want to know if you understand that you cannot store a massive adjacency list in the RAM of a single machine.

The "Correct" Practical Answer:

Storage: You cannot store the graph in memory. You store the adjacency list in a distributed Key-Value store (like BigTable or Cassandra). Key = Node ID, Value = List of Neighbors.

Processing:

If you need a specific path (BFS): You use a distributed queue (like Kafka) to manage the "frontier" of nodes to visit.

If you need to process the whole graph (like Longest Chain): You use MapReduce or Spark.

Map Step: Emit key-value pairs for edges.

Reduce Step: Aggregate connections and calculate path lengths iteratively.

The practical answer leverages MapReduce logic:

1. Bucket by Length: You cannot find a predecessor for a 5-letter word anywhere except in the 4-letter bucket.

2. Distributed Processing: You can process all 4-letter words on one server and all 5-letter words on another.

3. The MapReduce Job:

• Map: For every word of length $K$ (e.g., "apple"), generate all possible predecessors of length $K-1$ ("pple", "aple"...) as keys, with the value being the original word.
• Join/Reduce: Join these generated keys with the actual list of $K-1$ words to verify which connections actually exist.

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        # 1. Sort by length so we process shorter words first.
        #    This ensures that when we process a word, its potential
        #    predecessors have already been computed.
        words.sort(key=len)
        
        # 2. Dictionary to store the max chain length ending at each word.
        dp = {}
        max_chain = 1
        
        for word in words:
            # Initialize current word's chain length to 1 (the word itself)
            dp[word] = 1
            
            # 3. Try removing one character at every position to generate
            #    potential predecessors.
            for i in range(len(word)):
                prev_word = word[:i] + word[i+1:]
                
                # 4. If the generated predecessor exists in our DP map,
                #    update the chain length.
                if prev_word in dp:
                    dp[word] = max(dp[word], dp[prev_word] + 1)
            
            # Track the global maximum
            max_chain = max(max_chain, dp[word])
            
        return max_chain