We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest String Chain

Number: 1129

Difficulty: Medium

Paid? No

Companies: Citadel, Google, Atlassian, DE Shaw, Amazon, Bloomberg, MathWorks, Adobe, Apple, Two Sigma, Wix

Problem Description

Given an array of words, determine the length of the longest word chain where each word in the chain is a predecessor of the next. A word A is a predecessor of word B if by inserting exactly one letter anywhere in A without reordering the existing letters, you can form B.

Key Insights

  • Sort the words by length so that any potential predecessor appears before its longer successor.
  • Use dynamic programming where for each word, you calculate the maximum chain ending with that word by checking all possible words formed by deleting one letter.
  • A hash table (map/dictionary) allows you to quickly store and update the chain lengths for each word.
  • The final answer is the maximum chain length found over all words.

Space and Time Complexity

Time Complexity: O(N * L^2) where N is the number of words and L is the maximum word length. Space Complexity: O(N * L) due to storage in the hash table for chain lengths and intermediate strings.

Solution

The approach is to use dynamic programming. First, sort the words by their lengths so that any possible predecessor comes before the word itself. Then, initialize a hash table where the key is the word and the value is the longest chain ending at that word. For each word, generate all possible predecessors by deleting one character at a time, and if the predecessor exists in our hash table, update the current word’s chain length by taking the maximum chain value from its predecessors plus one. Finally, the answer is the maximum value stored in the hash table.

Code Solutions

# Function to compute the longest string chain using dynamic programming
def longestStrChain(words):
    # Sort words based on their length to ensure potential predecessors come first
    words.sort(key=len)
    # Dictionary to store the longest chain length ending with the word
    dp = {}
    max_chain = 1  # Minimum chain length is 1

    # Process each word in sorted order
    for word in words:
        current_length = 1  # Each word by itself is a chain of length 1
        # Try removing one letter at a time to form a potential predecessor
        for i in range(len(word)):
            # Form the predecessor by skipping the i-th letter
            predecessor = word[:i] + word[i+1:]
            # If predecessor exists, update current chain length
            if predecessor in dp:
                current_length = max(current_length, dp[predecessor] + 1)
        # Save the computed chain length for the current word
        dp[word] = current_length
        # Update the overall maximum chain length
        max_chain = max(max_chain, current_length)
        
    return max_chain

# Example usage:
words = ["a", "b", "ba", "bca", "bda", "bdca"]
print(longestStrChain(words))  # Expected output: 4
← Back to All Questions