Longest String Chain

JavaView on GFG

Intuition

Longest chain of words where each word adds one letter to the previous. DP with sorted lengths.

Algorithm

1Sort by length. dp[word] = max(dp[pred]+1) for all predecessors obtained by removing one char.

Common Pitfalls

•Same as LC 1048. Try removing each character from current word to find predecessor. O(n*L^2) where L = max word length.

Longest String Chain.java

Java

// Approach: Sort by word length. DP: for each word, try removing each character and check if predecessor is in chain.
// Time: O(n * len^2) Space: O(n * len)
class Solution {
    public int longestStringChain(String words[]) {
        // Step 1: Sort the words by their lengths
        Arrays.sort(words, (a, b) -> a.length() - b.length());

        // Step 2: Create a map to store the longest chain length for each word
        Map<String, Integer> dp = new HashMap<>();
        int maxLength = 1; // At least one word in the chain

        // Step 3: Process each word
        for (String word : words) {
            int currentLength = 1; // Start with a chain of length 1 (the word itself)

            // Generate all possible predecessors by removing one character
            for (int i = 0; i < word.length(); i++) {
                String predecessor = word.substring(0, i) + word.substring(i + 1);

                // Check if the predecessor exists in the map
                if (dp.containsKey(predecessor))
                    currentLength = Math.max(currentLength, dp.get(predecessor) + 1);
            }

            // Update the DP map with the current word's chain length
            dp.put(word, currentLength);

            // Update the maximum chain length
            maxLength = Math.max(maxLength, currentLength);
        }

        return maxLength;
    }
}

Was this solution helpful?