Longest String Chain

Dynamic Programming LIS Easy

Given an array of strings words[], the task is to return the longest string chain. A string chain is defined as a sequence of words where:

Each word (except the first) can be formed by inserting exactly one character into the previous word.

The first word of the chain can be any word from the words[] array.

The task is to determine the length of the longest chain.

Examples:

Input: words = ["a", "ab", "abc", "abcd", "abcde"]

Output: 5

Explanation: The longest chain is ["a", "ab", "abc", "abcd", "abcde"].

Each word in the chain is formed by adding exactly one character to the previous word.

Input: words = ["dog", "dogs", "dots", "dot", "d", "do"]

Output: 4

Explanation: The longest chain is ["d", "do", "dot", "dots"].

Each word is formed by inserting one character into the previous word.

Input: words = ["a", "aa", "aaa", "aaaa", "b", "bb", "bbb"]

Constraints

1 <= words.length <= 1000
1 <= words[i].length <= 20
words[i] only consists of lowercase English letters.

Hints

A Dynamic Programming (DP) approach efficiently solves this problem by Sorting words[] by length ensures that every word comes after all potential predecessors.
"Using a DP array (dp[word]) to store the longest chain ending at each word. Iterating through each word and checking all possible predecessors by removing one character at a time."

Editorial

A naive approach to solve this problem is to generate all the possible chains of string (using Power Set or Recursion method), and then store the longest among them. Clearly, this approach will not be a useful approach for the given problem as it will end up taking O(2^N), where N is the number of elements in the given array, i.e., exponential time complexity.

Recusion

Intuition:

The idea is to generate all possible increasing subsequences and find the length of the longest among them. As we need to find all possible subsequences, recusion can be used to solve the problem.

Approach:

Steps to form the recursive solution:

Express the problem in terms of indices: Let us define a function f(ind) that represents the length of the Longest Increasing Subsequence (LIS) starting from ind. Ultimately, the result will be the f(0).
The problem is now reduced to calculating f(0).
Try all possible choices for each index: At each index ind, we consider whether the current element should extend a previous subsequence or not. This gives an idea to introduce another parameter prev_ind in the function such that the following two possibilities arise:
- Not Take case (If arr[prev_ind] >= arr[ind]): In such case, the current element cannot be taken into consideration because the goal is to form an increasing subsequence. Since the element is not taken, the prev_ind remains the same and the call simply jumps to the next index i.e., f(ind+1, prev_ind).
- Take case (If arr[prev_ind] < arr[ind]): In such case, the current element can be added to the previously considered subsequence (ending at prev_ind) thus increasing the length of LIS by 1 and the call simply jumps to func(ind + 1, ind).
  
  Note that, the prev_ind is updated to ind, as now the ind becomes the last selected index for the further subsequence.
- Initial case when the subsequence is empty: Initially, when the function call begins, there is no element chosen for the subsequence. To mark this, prev_ind can be set as -1 representing that the current element will be the first element that will be taken into consideration.
  
  Hence, to get the answer, the initial function call must be f(0, -1).
Return the longest length of LIS found:After the take and notTake calls, the longest length of the subsequence found can be returned as the answer to the current function call.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

/* Function to return the length of LIS starting from 
index i with the element prev_ind element refers to
the previously selected element in the subsequence*/
func(int i, int prev_ind, int arr[]) {
    
    // Not Take case
    int notTake = func(i+1, prev_ind, arr);
    
    // Take case
    int take = 0;
    
    // If no element is chosen till now
    if(prev_ind == -1)
        take = func(i+1, i, arr) + 1;
    
    /* Else the current element can be 
    taken if it is strictly increasing */
    else if(arr[i] > arr[prev_ind])
        take = func(i+1, i, arr) + 1;
    
    // Return the maximum length obtained from both cases
    return max(take, notTake);
}

Base cases:

When the function call reaches the last index, the base case will be called and there will be two cases:

Take case: If the last index element is greater than the prev_ind element in the subsequnce or if the last index element is the first element in the subsequence, it can be taken in the subsequence and 1 can be returned.
Not Take case: Otherwise, the last index element can not be considered and 0 can be returned.

Solution (Recursive):

Note that submitting the following solution will result in Time Limit Exceeded.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        unordered_map<std::string, int> chains;  // Stores the max chain length for each word
        vector<std::string> sortedWords = words;
        sort(sortedWords.begin(), sortedWords.end(), [](const std::string& a, const std::string& b) {
            return a.length() < b.length();  // Sort words by length
        });

        for (const std::string& word : sortedWords) {
            chains[word] = 1;  // Initialize the chain length for the current word

            for (int i = 0; i < word.length(); i++) {
                std::string pred = word.substr(0, i) + word.substr(i + 1);  // Generate predecessor by removing one character
                if (chains.find(pred) != chains.end()) {
                    chains[word] = std::max(chains[word], chains[pred] + 1);
                }
            }
        }

        int maxChainLength = 0;
        for (const auto& entry : chains) {
            maxChainLength = std::max(maxChainLength, entry.second);
        }

        return maxChainLength;        
    }
};


int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    // Creating an object of Solution class
    Solution sol;
    int lengthOfLIS = sol.LIS(nums);
    
    cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    public int longestStrChain(String[] words) {
        Map<String, Integer> chains = new HashMap<>();  // Stores the max chain length for each word
        String[] sortedWords = Arrays.copyOf(words, words.length);
        Arrays.sort(sortedWords, (a, b) -> a.length() - b.length());  // Sort words by length

        for (String word : sortedWords) {
            chains.put(word, 1);  // Initialize the chain length for the current word

            for (int i = 0; i < word.length(); i++) {
                String pred = word.substring(0, i) + word.substring(i + 1);  // Generate predecessor by removing one character
                if (chains.containsKey(pred)) {
                    chains.put(word, Math.max(chains.getOrDefault(word, 0), chains.get(pred) + 1));
                }
            }
        }

        int maxChainLength = chains.values().stream().mapToInt(Integer::intValue).max().orElse(0);
        return maxChainLength;        
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        
        // Creating an object of Solution class
        Solution sol = new Solution();
        int lengthOfLIS = sol.LIS(nums);
        
        System.out.println("The length of the LIS for the given array is: " + lengthOfLIS);
    }
}
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        chains = {}  # Stores the max chain length for each word
        sorted_words = sorted(words, key=len) # Sort words by length

        for word in sorted_words:
            chains[word] = 1  # Initialize the chain length for the current word
            
            for i in range(len(word)):
                # Generate predecessor by removing one character
                pred = word[:i] + word[i+1:]  
                if pred in chains:
                    chains[word] = max(chains[word], chains[pred] + 1)

        return max(chains.values())

# Example usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]

# Creating an object of Solution class
sol = Solution()
lengthOfLIS = sol.LIS(nums)

print("The length of the LIS for the given array is:", lengthOfLIS)
var longestStrChain = function(words) {
    const chains = new Map();  // Stores the max chain length for each word
    const sortedWords = words.slice().sort((a, b) => a.length - b.length);  // Sort words by length

    for (const word of sortedWords) {
        chains.set(word, 1);  // Initialize the chain length for the current word

        for (let i = 0; i < word.length; i++) {
            const pred = word.slice(0, i) + word.slice(i + 1);  // Generate predecessor by removing one character
            if (chains.has(pred)) {
                chains.set(word, Math.max(chains.get(word) || 0, chains.get(pred) + 1));
            }
        }
    }

    return Math.max(...Array.from(chains.values()));  // Return the maximum chain length    
};

// Example usage
let nums = [10, 9, 2, 5, 3, 7, 101, 18];

// Creating an object of Solution class
let sol = new Solution();
let lengthOfLIS = sol.LIS(nums);

console.log("The length of the LIS for the given array is:", lengthOfLIS);

Complexity Analysis:

Time Complexity: O(2^N), where N represents the number of elements in the given array
In each function call, two recursive calls are made (take and not take) resulting in an exponential time complexity.

Space Complexity: O(N), because of the recursion stack space.

Memoization

If you draw the recursion tree, you will see that there are overlapping subproblems. Hence the DP approache can be applied to the recursive solution to optimise it.

Steps to convert the recursive solution to the Memoization solution:

Declare a dp array of size [n][n]: There are two states of dp which are:
- ind: which can go from 0 to n-1, requiring a total of n indices.
- prev_ind: which can go from -1 to n-2, requiring a total of (n-2 -(-1) +1) or n states.
Important:
Note that there is no index as -1, hence, to store the state (prev_ind = -1), it is required to do a co-ordinate shift. We can map the -1 index to 0, 0 index to 1, and so on....

Hence, a 2D dp array is needed where dp[ind][prev_ind+1] stores the result of the function call func(ind, prev_ind). The dp array stores the calculations of subproblems hence it is initialized with -1, to indicate that no subproblem has been solved yet.
While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet (the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array before returning the function call.

Note

Note that submitting the following code will throw a runtime error because of the tight constraints set for the problem. N can go upto 10⁵ and declaring a 2D dp of size N*N will require 10¹⁰ space causing Memory Limit Exceeded resulting in runtime error.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        unordered_map<std::string, int> chains;  // Stores the max chain length for each word
        vector<std::string> sortedWords = words;
        sort(sortedWords.begin(), sortedWords.end(), [](const std::string& a, const std::string& b) {
            return a.length() < b.length();  // Sort words by length
        });

        for (const std::string& word : sortedWords) {
            chains[word] = 1;  // Initialize the chain length for the current word

            for (int i = 0; i < word.length(); i++) {
                std::string pred = word.substr(0, i) + word.substr(i + 1);  // Generate predecessor by removing one character
                if (chains.find(pred) != chains.end()) {
                    chains[word] = std::max(chains[word], chains[pred] + 1);
                }
            }
        }

        int maxChainLength = 0;
        for (const auto& entry : chains) {
            maxChainLength = std::max(maxChainLength, entry.second);
        }

        return maxChainLength;        
    }
};


int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    // Creating an object of Solution class
    Solution sol;
    int lengthOfLIS = sol.LIS(nums);
    
    cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    public int longestStrChain(String[] words) {
        Map<String, Integer> chains = new HashMap<>();  // Stores the max chain length for each word
        String[] sortedWords = Arrays.copyOf(words, words.length);
        Arrays.sort(sortedWords, (a, b) -> a.length() - b.length());  // Sort words by length

        for (String word : sortedWords) {
            chains.put(word, 1);  // Initialize the chain length for the current word

            for (int i = 0; i < word.length(); i++) {
                String pred = word.substring(0, i) + word.substring(i + 1);  // Generate predecessor by removing one character
                if (chains.containsKey(pred)) {
                    chains.put(word, Math.max(chains.getOrDefault(word, 0), chains.get(pred) + 1));
                }
            }
        }

        int maxChainLength = chains.values().stream().mapToInt(Integer::intValue).max().orElse(0);
        return maxChainLength;        
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        
        // Creating an object of Solution class
        Solution sol = new Solution();
        int lengthOfLIS = sol.LIS(nums);
        
        System.out.println("The length of the LIS for the given array is: " + lengthOfLIS);
    }
}
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        chains = {}  # Stores the max chain length for each word
        sorted_words = sorted(words, key=len) # Sort words by length

        for word in sorted_words:
            chains[word] = 1  # Initialize the chain length for the current word
            
            for i in range(len(word)):
                # Generate predecessor by removing one character
                pred = word[:i] + word[i+1:]  
                if pred in chains:
                    chains[word] = max(chains[word], chains[pred] + 1)

        return max(chains.values())

# Example usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]

# Creating an object of Solution class
sol = Solution()
lengthOfLIS = sol.LIS(nums)

print("The length of the LIS for the given array is:", lengthOfLIS)
var longestStrChain = function(words) {
    const chains = new Map();  // Stores the max chain length for each word
    const sortedWords = words.slice().sort((a, b) => a.length - b.length);  // Sort words by length

    for (const word of sortedWords) {
        chains.set(word, 1);  // Initialize the chain length for the current word

        for (let i = 0; i < word.length; i++) {
            const pred = word.slice(0, i) + word.slice(i + 1);  // Generate predecessor by removing one character
            if (chains.has(pred)) {
                chains.set(word, Math.max(chains.get(word) || 0, chains.get(pred) + 1));
            }
        }
    }

    return Math.max(...Array.from(chains.values()));  // Return the maximum chain length    
};

// Example usage
let nums = [10, 9, 2, 5, 3, 7, 101, 18];

// Creating an object of Solution class
let sol = new Solution();
let lengthOfLIS = sol.LIS(nums);

console.log("The length of the LIS for the given array is:", lengthOfLIS);

Complexity Analysis:

Time Complexity: O(N²), where N is the size of the array
Because there will be a total of N*N states for which the function will be called.

Space Complexity: O(N²), because of the 2D dp array created taking O(N²) space and O(N) recursive stack space.

Code

Problem List

Longest String Chain

Examples:

Constraints

Hints

Editorial

Recusion

Intuition:

Approach:

Steps to form the recursive solution:

Base cases:

Solution (Recursive):

Complexity Analysis:

Memoization

Steps to convert the recursive solution to the Memoization solution:

Important:

Note

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code