#1048

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest String Chain

Find the longest word chain by scanning arrays and using hash lookups to efficiently track predecessor-successor sequences in words.

array hash table two pointers string dynamic programming

Problem Statement

You are given an array of words where each word consists of lowercase English letters. A word wordA is considered a predecessor of wordB if you can insert exactly one letter anywhere in wordA without changing the relative order of the other characters to produce wordB. The goal is to determine the length of the longest possible word chain from the given array.

A word chain is a sequence of words [word1, word2, ..., wordk] where k >= 1, and each word is a predecessor of the next. A single word counts as a valid chain of length 1. For example, in words = ["a","b","ba","bca","bda","bdca"], one longest chain is ["a","ba","bda","bdca"] with length 4.

Examples

Example 1

Input: words = ["a","b","ba","bca","bda","bdca"]

Output: 4

One of the longest word chains is ["a","ba","bda","bdca"].

Example 2

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]

Output: 5

All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3

Input: words = ["abcd","dbqca"]

Output: 1

The trivial word chain ["abcd"] is one of the longest word chains. ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

Constraints

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of lowercase English letters.

Solution Approach

Sort Words by Length

Start by sorting the words array by word length. This ensures that when scanning words, all potential predecessors of a word have already been processed and stored in the hash map, which is crucial for correctly computing the longest chain in one pass.

Use Hash Map to Track Chains

Maintain a hash map where each word maps to the length of the longest chain ending with that word. For each word, try deleting one character at every position to form a predecessor candidate. If the candidate exists in the hash map, update the current word's chain length to be one more than the predecessor's chain.

Compute Maximum Chain

After processing all words, the maximum value in the hash map represents the length of the longest string chain. This avoids redundant recomputation and leverages the array scanning plus hash lookup pattern efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N * L^2), where N is the number of words and L is the maximum word length, since each word can generate up to L predecessor candidates. Space complexity is O(N * L) for storing words in the hash map and their chain lengths.

What Interviewers Usually Probe

They may ask why we delete characters instead of inserting them during chain building.
Expect discussion on time-space trade-offs using hash maps versus dynamic programming arrays.
Clarify handling of words with the same length but different character order to avoid invalid chains.

Common Pitfalls or Variants

Common pitfalls

Failing to sort words by length, which can lead to incorrect predecessor evaluation.
Using insertion instead of deletion, which complicates finding valid predecessor words.
Overwriting chain lengths without checking all predecessor candidates, missing longer chains.

Follow-up variants

Find all longest chains instead of just the length, returning sequences of words.
Modify constraints to allow uppercase letters and non-English alphabets, requiring extended hash handling.
Count the number of distinct longest chains instead of maximum length.

FAQ

What is the main pattern to solve Longest String Chain?

The key pattern is array scanning plus hash lookup, using deletion of characters to map predecessors and compute the maximum chain efficiently.

Can I insert characters instead of deleting to find chains?

While insertion is theoretically equivalent, deleting one character from the current word simplifies hash lookup and avoids scanning unnecessary combinations.

Do words with the same length affect the solution?

Yes, words of the same length should be processed individually, as they cannot be predecessors of each other, ensuring valid chain construction.

What is the time complexity for the solution?

Time complexity is O(N * L^2), where N is the number of words and L is the maximum word length, due to generating all possible predecessors per word.

Is sorting necessary before computing chains?

Yes, sorting words by length guarantees that all potential predecessors are already in the hash map when processing a word, avoiding incorrect chain lengths.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        def check(w1, w2):
            if len(w2) - len(w1) != 1:
                return False
            i = j = cnt = 0
            while i < len(w1) and j < len(w2):
                if w1[i] != w2[j]:
                    cnt += 1
                else:
                    i += 1
                j += 1
            return cnt < 2 and i == len(w1)

        n = len(words)
        dp = [1] * (n + 1)
        words.sort(key=lambda x: len(x))
        res = 1
        for i in range(1, n):
            for j in range(i):
                if check(words[j], words[i]):
                    dp[i] = max(dp[i], dp[j] + 1)
            res = max(res, dp[i])
        return res

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        def check(w1, w2):
            if len(w2) - len(w1) != 1:
                return False
            i = j = cnt = 0
            while i < len(w1) and j < len(w2):
                if w1[i] != w2[j]:
                    cnt += 1
                else:
                    i += 1
                j += 1
            return cnt < 2 and i == len(w1)

        n = len(words)
        dp = [1] * (n + 1)
        words.sort(key=lambda x: len(x))
        res = 1
        for i in range(1, n):
            for j in range(i):
                if check(words[j], words[i]):
                    dp[i] = max(dp[i], dp[j] + 1)
            res = max(res, dp[i])
        return res

Continue Practicing

#792 number of matching subsequences #522 longest uncommon subsequence ii #1169 invalid transactions