PPractick

The problem

You're building a word-game feature (similar to a "word ladder" mode) for a vocabulary app. A word A is a predecessor of word B if you can insert exactly one letter into A (anywhere) to form B, without reordering the other letters. A string chain is a sequence of words word1 -> word2 -> ... -> wordk where each word is a predecessor of the next. Your task: given a list of words, find the length of the longest possible chain you can build (words can be reordered/picked in any order to form the chain, but each must be exactly one-insertion apart from the previous).

Example: ["a","b","ba","bca","bda","bdca"] — the chain "a" -> "ba" -> "bda" -> "bdca" has length 4.

Function signature

int longestStrChain(vector<string>& words);

Test cases

Input words	Output	Explanation
["a","b","ba","bca","bda","bdca"]	4	"a" -> "ba" -> "bda" -> "bdca"
["xbc","pcxbcf","xb","cxbc","pcxbc"]	5	"xb" -> "xbc" -> "cxbc" -> "pcxbc" -> "pcxbcf"
["abcd","dbqca"]	1	"dbqca" needs 2 insertions from "abcd", not a valid predecessor step
["a"]	1	Single word, chain of length 1
[]	0	Empty input
["ab","abc","abcd","abcde"]	4	Each word extends the previous by exactly one letter, in order

(Always confirm: words can be any length, duplicates possible, and a single word alone counts as a chain of length 1.)

How interviewers phrase it

• "Given a list of words, find the longest chain where each word is formed by inserting one character into the previous word."
• "Think of it like a word ladder, but insertion-only, and words don't need to be adjacent in the input array — you can pick any order."
• May be phrased around "word building" games or "which word can absorb the most single-letter insertions in sequence."

Clarifying questions to ask

1. Does "predecessor" mean exactly one character inserted anywhere (not just appended at the end), with the rest of the letters staying in the same relative order? (Confirm — this is the key constraint.)
2. Are there duplicate words in the input? Should duplicates be treated as distinct chain links or collapsed?
3. Is the alphabet just lowercase English letters, or can it include other characters?
4. What's the expected size of words and max word length? (Helps decide if O(n² * L) — comparing all pairs — is acceptable, or if the "remove one character and hash" trick is expected for efficiency.)
5. Should the returned value be the chain length (number of words), or the number of insertions (length - 1)? (Confirm — this problem wants word count.)

Follow-ups to expect

1. "Can you return the actual chain of words, not just the length?"
2. "Why did you sort by word length first — is that necessary?"
3. "How is this related to Longest Increasing Subsequence?"
4. "Can you avoid the O(n²) pairwise predecessor check?"
5. "What if insertions could happen at both ends only, not anywhere in the middle?"
6. "What's the time complexity of checking if one word is a predecessor of another, and how does word length affect your overall complexity?"

Related questions

• Longest Increasing Subsequence Medium
• Print Longest Increasing Subsequence Medium
• Longest Increasing Subsequence (DP-43) Medium
• Largest Divisible Subset Medium
• Longest Bitonic Subsequence Medium
• Number of Longest Increasing Subsequences Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in