Longest String Chain
Asked at Atlassian
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | MEDIUM | View all Atlassian questions → |
How to Think About It
Sort words by length so shorter words come before longer ones
Use a hash map to store the longest chain ending at each word
For each word, try removing one character at a time to find predecessors
If a predecessor exists in the map, extend its chain length by one
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.
What Trips People Up in Real Interviews
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
Solution Code
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 resFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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