Solved Longest String Chain problem using DP on GeeksforGeeks

🚀 Day 111 of #160DaysOfCode ✅ Topic: Dynamic Programming — Longest String Chain 💡 Platform: GeeksforGeeks (Problem: Longest String Chain) 🧠 Concept Learned: Today I solved the Longest String Chain problem using Dynamic Programming. The goal was to find the longest sequence of words where each word can be formed by adding exactly one letter to the previous word, without changing the order of characters. 📘 Approach Used: Sort all words by length (shorter first). Use a dictionary (dp) to store the longest chain ending at each word. For each word, generate all possible predecessors by removing one character at a time. If the predecessor exists in dp, update: dp[word] = max(dp[word], dp[pred] + 1) Keep track of the maximum chain length in res. 🧩 Example: Input: ["a", "b", "ba", "bca", "bda", "bdca"] Output: 4 Explanation: The longest chain is a → ba → bda → bdca ✅ Result: All test cases passed (1114 / 1114) 🎯 Understood how sorting + dynamic programming + string manipulation can be combined to solve complex sequence problems efficiently.

  • graphical user interface, text

To view or add a comment, sign in

Explore content categories