1048. Longest String Chain LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 1048. Longest String Chain LeetCode Solution with the best time and space complexity. The solution to Longest String Chain problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest String Chain solution in C++
Longest String Chain solution in Java
Longest String Chain solution in Python
Additional Resources

1048. Longest String Chain LeetCode Solution image

Problem Statement of Longest String Chain

You are given an array of words where each word consists of lowercase English letters.
wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

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

A word chain is a sequence of words [word1, word2, …, wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, 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.

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.

Complexity Analysis

Time Complexity: O(n\max(|\texttt{words[i]}|)^2)
Space Complexity: O(n)

1048. Longest String Chain LeetCode Solution in C++

class Solution {
 public:
  int longestStrChain(vector<string>& words) {
    const unordered_set<string> wordsSet{words.begin(), words.end()};
    unordered_map<string, int> mem;
    return accumulate(words.begin(), words.end(), 0,
                      [&](int acc, const string& word) {
      return max(acc, longestStrChain(word, wordsSet, mem));
    });
  }

 private:
  // Returns the longest string chain, where s is the last word.
  int longestStrChain(const string& s, const unordered_set<string>& wordsSet,
                      unordered_map<string, int>& mem) {
    if (const auto it = mem.find(s); it != mem.cend())
      return it->second;

    int res = 1;

    for (int i = 0; i < s.length(); ++i) {
      const string pred = s.substr(0, i) + s.substr(i + 1);
      if (wordsSet.contains(pred))
        res = max(res, longestStrChain(pred, wordsSet, mem) + 1);
    }

    return mem[s] = res;
  }
};
/* code provided by PROGIEZ */

1048. Longest String Chain LeetCode Solution in Java

class Solution {
  public int longestStrChain(String[] words) {
    Set<String> wordsSet = new HashSet<>(Arrays.asList(words));
    int ans = 0;

    for (final String word : words)
      ans = Math.max(ans, longestStrChain(word, wordsSet));

    return ans;
  }
  // dp[s] := the longest string chain, where s is the last word
  private Map<String, Integer> dp = new HashMap<>();

  private int longestStrChain(final String s, Set<String> wordsSet) {
    if (dp.containsKey(s))
      return dp.get(s);

    int ans = 1;

    for (int i = 0; i < s.length(); ++i) {
      final String pred = s.substring(0, i) + s.substring(i + 1);
      if (wordsSet.contains(pred))
        ans = Math.max(ans, longestStrChain(pred, wordsSet) + 1);
    }

    dp.put(s, ans);
    return ans;
  }
}
// code provided by PROGIEZ

1048. Longest String Chain LeetCode Solution in Python

class Solution:
  def longestStrChain(self, words: list[str]) -> int:
    wordsSet = set(words)

    @functools.lru_cache(None)
    def dp(s: str) -> int:
      """Returns the longest chain where s is the last word."""
      ans = 1
      for i in range(len(s)):
        pred = s[:i] + s[i + 1:]
        if pred in wordsSet:
          ans = max(ans, dp(pred) + 1)
      return ans

    return max(dp(word) for word in words)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents