LeetCode 1048 Longest String Chain - Walkthrough

A word chain where each word is the previous plus one letter. Sort words by length, then DP. For each word, try removing each character. If the resulting word exists and has a chain value, extend from it. Example: $[\text{"a"}, \text{"ba"}, \text{"bda"}, \text{"bdca"}]$. Chain: a → ba → bda → bdca. Length $4$. Use a hashmap for $O(1)$ lookup. Time: $O(n \cdot L^2)$

Time complexity: $O(n \cdot L^2)$ where $L$ is max word length (for each word, try $L$ removals, each taking $O(L)$).

Space complexity: $O(n \cdot L)$ for the hash map.