MediumArrayHash TableTwo PointersStringDynamic ProgrammingSortingUpdated Sep 2026

1048. Longest String Chain

Asked at Atlassian

Difficulty

Medium

Time

O(n * L^2)

Space

O(n * L)

Pattern

Array

Companies

1

Problem

You get a list of words, all in lowercase English letters. A word A is a predecessor of word B if you can add exactly one letter somewhere inside A (keeping the other letters in the same order) and get B. For example, "abc" is a predecessor of "abac", but "cba" is not a predecessor of "bcad" because the letter order changed.

A word chain is a list of words [w1, w2, ..., wk] where each word is a predecessor of the next one. A chain with just one word is allowed. All words in the chain must come from the given list, and you may not reuse a word twice.

Return the length of the longest chain you can build. If no two words can be linked, the answer is 1.

What a chain looks like

chainababdabdca0123Length 4 chain: each word is one letter longer thanthe word before it."a" + 'b' = "ba""ba" + 'd' = "bda""bda" + 'c' = "bdca"
Each step adds exactly one letter and keeps the order of the other letters, so the chain grows by one character at a time.

Constraints

  • ●1 <= words.length <= 1000
  • ●1 <= words[i].length <= 16
  • ●words[i] contains only lowercase English letters

Examples

Example 1
Inputwords = ["a","b","ba","bca","bda","bdca"]
Output4
WhyThe chain ["a","ba","bda","bdca"] works: "a" → "ba" adds 'b', "ba" → "bda" adds 'd', "bda" → "bdca" adds 'c'. That is 4 words, and no longer chain exists.
Example 2
Inputwords = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output5
WhyEvery word can be used: "xb" → "xbc" (add 'c') → "cxbc" (add 'c' at front) → "pcxbc" (add 'p') → "pcxbcf" (add 'f'). That gives a chain of length 5.
Example 3
Inputwords = ["abcd","dbqca"]
Output1
Why"dbqca" is longer, but you cannot get it by inserting one letter into "abcd" — the letters are in a different order. So no chain of length 2 exists, and the best is a single word.

Asked At

1 companies
CompanyDifficulty
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Sort words by length so shorter words come before longer ones

2

Use a hash map to store the longest chain ending at each word

3

For each word, try removing one character at a time to find predecessors

4

If a predecessor exists in the map, extend its chain length by one

5

Track the global maximum chain length across all words

Optimal Approach

Sort the words by length in ascending order. Create a hash map where each word maps to the longest chain ending at that word, initialized to 1 for all words. For each word in sorted order, try removing each character to form all possible predecessors. If a predecessor exists in the map, update the current word chain length as max(current, predecessor + 1). The answer is the maximum value in the map. Sorting ensures that when we process a word, all shorter words (potential predecessors) have already been processed. This runs in O(n * L^2) time where n is the number of words and L is the maximum word length.

Sort by length, then try deleting one letter

sorted wordsabbabcabdabdca012345currSorting by length guarantees every possiblepredecessor is already processed.word = "bdca"delete 'b' → "dca" (not in dp)delete 'd' → "bca" (in dp = 2)delete 'c' → "bda" (in dp = 3)dp["bdca"] = 3 + 1 = 4Try every single-letter deletion; the best predecessorfound gives the new chain length.dp mapwordbest chain012345a1b1ba2bca2bda3bdca4The map stores the longest chain ending at each word;the answer is the largest value.dp[w] = 1 + max(dp[pred])pred = w with one letter removedanswer = max(dp.values())
Process words from short to long. For each word, delete one character at a time and look up the result in the dp map.
ComplexityTime O(n * L^2)Space O(n * L)For each of the n words we try L deletions, and each deletion builds a new string of length up to L; the hash map stores at most n words of length L.

What Trips People Up in Real Interviews

1

Always sort by word length first so DP dependencies are resolved in order

2

Clarify that a predecessor must be exactly one character shorter

3

Use a dictionary/set for O(1) predecessor lookup instead of nested loops

4

Handle duplicates in the input by deduplicating or allowing same-length chains

5

Discuss that total work is O(n * L^2) where L is average word length

Solution Code

O(n * L^2) time
def longestStrChain(words):
    words.sort(key=len)
    dp = {}
    res = 1
    for word in words:
        dp[word] = 1
        for i in range(len(word)):
            pred = word[:i] + word[i + 1:]
            if pred in dp:
                dp[word] = max(dp[word], dp[pred] + 1)
        res = max(res, dp[word])
    return res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Longest String Chain problem?

Given a list of words, find the length of the longest word chain where each word in the chain is formed by adding exactly one letter to the previous word. Words in the chain must come from the original list. This problem combines sorting, hashing, and dynamic programming.

How do you solve Longest String Chain?

The optimal approach runs in O(n * L^2) time and O(n * L) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Longest String Chain?

Longest String Chain is asked at Atlassian. It is a medium difficulty problem.

What are common mistakes on Longest String Chain?
  • Always sort by word length first so DP dependencies are resolved in order
  • Clarify that a predecessor must be exactly one character shorter
  • Use a dictionary/set for O(1) predecessor lookup instead of nested loops
  • Handle duplicates in the input by deduplicating or allowing same-length chains
  • Discuss that total work is O(n * L^2) where L is average word length