Vultr DocsLatest Content

Longest String Chain

Updated on 05 June, 2025
Longest String Chain header image

Problem Statement

In this task, you are given an array named words that contains various words composed of lowercase English letters. Your aim is to determine the length of the longest word chain that can be formed using the given list. A word chain is a sequence where each word is a predecessor of the next one. A word wordA is considered a predecessor of wordB if wordA can be transformed into wordB by inserting exactly one letter at any position, without rearranging any of the original letters in wordA. The goal is to identify the maximum length of such a chain in the provided list of words.

Examples

Example 1

Input:

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

Output:

4

Explanation:

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

Example 2

Input:

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

Output:

5

Explanation:

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

Example 3

Input:

words = ["abcd","dbqca"]

Output:

1

Explanation:

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.

Approach and Intuition

Understanding how to form the longest word chain involves determining relationships between words based on specific transformation rules. Here's a step-by-step approach and the intuition behind solving this problem:

  1. Sorting Words by Length:

    • Begin by sorting the words based on their length. This simple step helps prioritize shorter words that potentially start a word chain leading to longer versions.

  2. Using Dynamic Programming:

    • Utilize a dynamic programming approach where you keep track of the longest chain that ends at each word. You do this with the help of a dictionary where the keys are words and the values are the lengths of the longest chains ending with those words.

  3. Building Relationships:

    • For each word, try creating all possible words that could have led to it by removing one character at a time. This step checks for potential predecessors.
    • For each generated potential predecessor, if it exists in the list and can be used to extend an existing chain, update your dictionary's chain length for the current word.

  4. Calculating the Maximum Length:

    • As you iterate and update potential chains, continually track the maximum length observed in your dictionary.

This approach steadily builds up potential sequences without needing to directly compare every word with every other word, making use of the predefined order induced by sorting and the efficient look-up capabilities of dictionaries. Each word is essentially "built" from its shorter predecessors, leading up to potentially the longest chain in the given list.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int longestWordChain(vector<string>& words) {
        unordered_map<string, int> wordMap;

        // Sort words by length
        sort(words.begin(), words.end(), [](const string& first, const string& second) {
            return first.size() < second.size();
        });

        int maxLength = 1;

        for (const string& word : words) {
            int currentLength = 1;
            // Check all substrings obtained by removing one letter
            for (int i = 0; i < word.size(); i++) {
                string newWord = word.substr(0, i) + word.substr(i + 1);
                if (wordMap.find(newWord) != wordMap.end()) {
                    currentLength = max(currentLength, wordMap[newWord] + 1);
                }
            }
            wordMap[word] = currentLength;
            maxLength = max(maxLength, currentLength);
        }
        return maxLength;
    }
};

The provided C++ solution aims to determine the longest possible string chain from a list of words, wherein each subsequent word in the chain can be formed by adding exactly one letter to a previous word. The procedure involves the following steps:

  • An unordered map (wordMap) is used to keep track of the longest chain length up to each word.
  • A sorting function sorts the list of words in ascending order by their lengths to facilitate the building of chains from shorter to longer words.
  • The main for-loop processes each word:
    • It initializes the current word's chain length (currentLength) to 1.
    • The inner for-loop generates potential predecessor words by removing one letter at a time from the current word (newWord).
    • If this newWord exists in wordMap, the code updates currentLength by comparing its current value with the chain length of newWord plus one.
    • After processing all possible newWords, the map is updated for the current word.
    • The maxLength variable, tracking the longest chain found, is continually updated during iterations.
  • Finally, the function returns maxLength, representing the length of the longest chain possible among the input words.

This logic efficiently builds upon smaller chains to construct possibly longer ones, ensuring that all combinations are explored by capitalizing on the characteristic benefits of hash maps for quick lookup.

java 
class Solution {
    public int maxStrChain(String[] wordsArray) {
        Map<String, Integer> hashmap = new HashMap<>();

        // Sort words by their length
        Arrays.sort(wordsArray, (s1, s2) -> s1.length() - s2.length());

        int maxSequence = 1;

        for (String currentWord : wordsArray) {
            int currentMax = 1;
            // Creating predecessors by removing each character from the word
            for (int index = 0; index < currentWord.length(); index++) {
                StringBuilder modified = new StringBuilder(currentWord);
                modified.deleteCharAt(index);
                String previousWord = modified.toString();
                int previousMax = hashmap.getOrDefault(previousWord, 0);
                currentMax = Math.max(currentMax, previousMax + 1);
            }
            hashmap.put(currentWord, currentMax);
            maxSequence = Math.max(maxSequence, currentMax);
        }
        return maxSequence;
    }
}

The Java solution provided addresses the problem of finding the Longest String Chain given an array of words. The approach uses dynamic programming to keep track of the maximum length sequence that can be formed.

Here’s a breakdown of the tasks performed by the code:

  • Initializes a hashmap to store each word and the longest chain that ends with that word.
  • Sorts the input array of words based on their lengths using a custom comparator in the Arrays.sort() method.
  • Iterates over each word in the sorted array. For each word, it tries to build possible predecessor words by removing one character at a time from the word.
  • For each generated predecessor, it checks if it exists in the hashmap. If it does, it calculates the maximum chain length using this predecessor.
  • Updates the hashmap with the maximum chain length found for the current word.
  • Continuously updates a variable maxSequence to ensure it holds the maximum length of any chain found during the traversal.

The code returns the maximum value of maxSequence, which represents the length of the longest possible string chain in the given list of words. This solution efficiently combines sorting and hashmap data structures to minimize computations and optimize look-ups.

Comments

No comments yet.