Longest String Chain - Practice Coding Problems

Longest String Chain - Problem

Array Hash Table Two Pointers String Dynamic Programming Sorting Medium

You are given an array of words where each word consists of lowercase English letters.

Word A is a predecessor of word B if and only if we can insert exactly one letter anywhere in word A without changing the order of the other characters to make it equal to word B.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word₁, word₂, ..., wordₖ] with k >= 1, where word₁ is a predecessor of word₂, word₂ is a predecessor of word₃, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Input & Output

Example 1 — Basic Chain

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

› Output: 4

💡 Note: One longest chain is: "a" → "ba" → "bca" → "bdca". Each word is formed by adding exactly one character to the previous word while maintaining order.

Example 2 — Multiple Chains

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

› Output: 5

💡 Note: The longest chain is: "xb" → "xbc" → "cxbc" → "pcxbc" → "pcxbcf". Length is 5.

Example 3 — Single Word

$ Input: words = ["abde","abc","abd","abcde","ade","ae","1abde","1abc","1abcde"]

› Output: 4

💡 Note: One longest chain is: "ae" → "ade" → "abde" → "abcde". Each step adds exactly one character.

Constraints

1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 16
words[i] only contains lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words with different lengths

Process

Find predecessor relationships and build chains

Output

Return length of longest possible chain

Key Takeaway

🎯 Key Insight: Sort by length first - predecessors are always shorter, making DP transitions clear

Asked in

G Google 45 a Amazon 38 M Microsoft 32 F Facebook 28

The optimal approach is to sort words by length and use dynamic programming. For each word, check all shorter words to find valid predecessors. Time: O(n² × L), Space: O(n) where n is number of words and L is average word length.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Chains	O(n! × L)	O(n)	Generate all possible word chains and find the longest one
Sort by Length + DFS	O(n² × L)	O(n)	Sort words by length, then use DFS with memoization to build chains
Dynamic Programming Bottom-Up	O(n² × L)	O(n)	Build chains from shortest to longest words using DP table

Brute Force - Try All Chains — Algorithm Steps

For each word as starting point
Recursively try to extend chain with all other words
Check if current word is predecessor of next word
Track maximum chain length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Try each word as chain start

Extend

For each word, try all others as next

Result

Return longest chain found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isPredecessor(const char* word1, const char* word2) {
    int len1 = strlen(word1), len2 = strlen(word2);
    if (len2 != len1 + 1) return false;
    
    int i = 0, j = 0;
    bool foundDiff = false;
    
    while (i < len1 && j < len2) {
        if (word1[i] == word2[j]) {
            i++; j++;
        } else {
            if (foundDiff) return false;
            foundDiff = true;
            j++;
        }
    }
    return true;
}

int dfs(const char* currentWord, char words[][20], int n, bool* used) {
    int maxChain = 1;
    for (int i = 0; i < n; i++) {
        if (!used[i] && isPredecessor(currentWord, words[i])) {
            used[i] = true;
            int chain = 1 + dfs(words[i], words, n, used);
            if (chain > maxChain) maxChain = chain;
            used[i] = false;
        }
    }
    return maxChain;
}

int solution(char words[][20], int n) {
    int result = 1;
    for (int i = 0; i < n; i++) {
        bool* used = (bool*)calloc(n, sizeof(bool));
        used[i] = true;
        int chain = dfs(words[i], words, n, used);
        if (chain > result) result = chain;
        free(used);
    }
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char words[1000][20];
    int n = 0;
    
    char* token = strtok(line, "[],\"");
    while (token != NULL && n < 1000) {
        if (strlen(token) > 0) {
            strcpy(words[n++], token);
        }
        token = strtok(NULL, "[],\"");
    }
    
    printf("%d\n", solution(words, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × L)

Factorial combinations of words, each requiring O(L) predecessor check

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n words

⚡ Linearithmic Space

125.0K Views

Medium-High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Chains — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler