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, the task is to return the length of the longest possible word chain with words chosen from the given list of words.
Examples:
Input: n = 6, words = [“a”, “b”, “ba”, “bca”, “bda”, “bdca”]
Output: 4
Explanation: One of the longest word chains is [“a”,”ba”,”bda”,”bdca”]Input: n = 2, words = [“abcd”,”dbqca”]
Output: 1
Explanation: The trivial word chain [“abcd”] is one of the longest word chains.
Longest String Chain using Map:
- Sort the input words by length to process shorter words before longer ones.
- Use an unordered_map to track the maximum chain length for each word (initialized to 1).
- Iterate through each word:
- For each character position, create a new word by removing that character.
- If the new word exists in the map, update the chain length for the current word as the maximum of the chain length of the new word plus one and the current chain length.
- Keep track of the maximum chain length found while iterating.
- The final result is the maximum chain length among all words.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Custom comparison function to sort// strings by their lengthsbool static cmp(string& a, string& b){ return a.size() < b.size();}// Function to find the length of// the longest string chainint longestStingChain(vector<string>& words){ // Sort the input words based on their // lengths using custom comparison function sort(words.begin(), words.end(), cmp); // Create an unordered map to store the // maximum chain length for each word unordered_map<string, int> unmap; // Initialize the result with a minimum // chain length of 1 int result = 1; // Iterate through each word in the // sorted list of words for (int i = 0; i < words.size(); i++) { // If the current word is not in the map, // add it with a chain length of 1 if (unmap.find(words[i]) == unmap.end()) unmap[words[i]]++; // Iterate through each character of // the current word for (int j = 0; j < words[i].size(); j++) { // Create a copy of the current word string copyCurrentWord = words[i]; // Remove one character at the j-th // position to create a new word string temp = copyCurrentWord.erase(j, 1); // If the new word is in the map, // update the chain length for // the current word if (unmap.find(temp) != unmap.end()) { unmap[words[i]] = max(unmap[temp] + 1, unmap[words[i]]); // Update the overall result with // the maximum chain length // found so far result = max(result, unmap[words[i]]); } } } // Return the maximum chain length found return result;}// Drivers codeint main(){ // Create a vector of strings containing // some example words vector<string> s = { "a", "b", "ba", "bca", "bda", "bdca" }; // Call the longestStingChain function // and print the result cout << longestStingChain(s); return 0;} |
Java
import java.util.*;public class GFG { // Custom comparison function to sort // strings by their lengths static class StringLengthComparator implements Comparator<String> { @Override public int compare(String a, String b) { return Integer.compare(a.length(), b.length()); } } // Function to find the length of // the longest string chain public static int longestStringChain(List<String> words) { // Sort the input words based on their lengths using custom comparison function words.sort(new StringLengthComparator()); // Create a map to store the maximum chain length for each word Map<String, Integer> chainLengths = new HashMap<>(); // Initialize the result with a minimum chain length of 1 int result = 1; // Iterate through each word in the sorted list of words for (String word : words) { chainLengths.put(word, 1); // Iterate through each character of the current word for (int j = 0; j < word.length(); j++) { // Create a copy of the current word StringBuilder copyCurrentWord = new StringBuilder(word); // Remove one character at the j-th position to create a new word copyCurrentWord.deleteCharAt(j); String temp = copyCurrentWord.toString(); // If the new word is in the map, update the chain length for the current word if (chainLengths.containsKey(temp)) { chainLengths.put(word, Math.max(chainLengths.get(temp) + 1, chainLengths.get(word))); // Update the overall result with the maximum chain length found so far result = Math.max(result, chainLengths.get(word)); } } } // Return the maximum chain length found return result; } public static void main(String[] args) { // Create a list of strings containing some example words List<String> words = Arrays.asList("a", "b", "ba", "bca", "bda", "bdca"); // Call the longestStringChain function and print the result System.out.println(longestStringChain(words)); }} |
Python3
# Custom comparison function to sort# strings by their lengthsdef cmp(a, b): return len(a) < len(b)# Function to find the length of# the longest string chaindef longestStringChain(words): # Sort the input words based on their # lengths using custom comparison function words.sort(key=lambda x: len(x)) # Create a dictionary to store the # maximum chain length for each word unmap = {} # Initialize the result with a minimum # chain length of 1 result = 1 # Iterate through each word in the # sorted list of words for word in words: # If the current word is not in the dictionary, # add it with a chain length of 1 if word not in unmap: unmap[word] = 1 # Iterate through each character of # the current word for j in range(len(word)): # Create a copy of the current word copyCurrentWord = list(word) # Remove one character at the j-th # position to create a new word temp = copyCurrentWord[:j] + copyCurrentWord[j+1:] # Convert the list back to a string temp = ''.join(temp) # If the new word is in the dictionary, # update the chain length for the current word if temp in unmap: unmap[word] = max(unmap[temp] + 1, unmap[word]) # Update the overall result with # the maximum chain length # found so far result = max(result, unmap[word]) # Return the maximum chain length found return result# Driver codeif __name__ == "__main__": # Create a list of strings containing # some example words s = ["a", "b", "ba", "bca", "bda", "bdca"] # Call the longestStringChain function # and print the result print(longestStringChain(s)) |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ // Function to find the length of the longest string chain static int LongestStringChain(List<string> words) { // Sort the input words based on their lengths using a lambda expression words.Sort((a, b) => a.Length.CompareTo(b.Length)); // Create a dictionary to store the maximum chain length for each word Dictionary<string, int> unmap = new Dictionary<string, int>(); // Initialize the result with a minimum chain length of 1 int result = 1; // Iterate through each word in the sorted list of words foreach (string word in words) { // If the current word is not in the dictionary, add it with a chain length of 1 if (!unmap.ContainsKey(word)) unmap[word] = 1; // Iterate through each character of the current word for (int j = 0; j < word.Length; j++) { // Create a copy of the current word string copyCurrentWord = word; // Remove one character at the j-th position to create a new word string temp = copyCurrentWord.Remove(j, 1); // If the new word is in the dictionary, update the chain length for the current word if (unmap.ContainsKey(temp)) { unmap[word] = Math.Max(unmap[temp] + 1, unmap[word]); // Update the overall result with the maximum chain length found so far result = Math.Max(result, unmap[word]); } } } // Return the maximum chain length found return result; } // Driver code static void Main() { // Create a list of strings containing some example words List<string> words = new List<string> { "a", "b", "ba", "bca", "bda", "bdca" }; // Call the LongestStringChain function and print the result Console.WriteLine(LongestStringChain(words)); }} |
Javascript
function longestStringChain(words) { // Sort the input words based on their lengths words.sort((a, b) => a.length - b.length); // Create a map to store the maximum chain length for each word const wordMap = new Map(); // Initialize the result with a minimum chain length of 1 let result = 1; // Iterate through each word in the sorted list of words for (const word of words) { // If the current word is not in the map, add it with a chain length of 1 if (!wordMap.has(word)) { wordMap.set(word, 1); } // Iterate through each character of the current word for (let j = 0; j < word.length; j++) { // Remove one character at the j-th position to create a new word const temp = word.slice(0, j) + word.slice(j + 1); // If the new word is in the map, update the chain length for the current word if (wordMap.has(temp)) { wordMap.set(word, Math.max(wordMap.get(temp) + 1 || 2, wordMap.get(word))); // Update the overall result with the maximum chain length found so far result = Math.max(result, wordMap.get(word)); } } } // Return the maximum chain length found return result;}// Example wordsconst words = ["a", "b", "ba", "bca", "bda", "bdca"];// Call the longestStringChain function and print the resultconsole.log(longestStringChain(words)); |
Output
4
Time Complexity: O(N * M)
Auxiliary Space: O(N * M);
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
