251. Longest String Chain

🔗 LeetCode Problem: 1048. Longest String Chain
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Two Pointers, String, Dynamic Programming, DP - LIS

Problem Statement

You are 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.

• For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3:

Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because letters are added more than one position.

Constraints: - 1 <= words.length <= 1000 - 1 <= words[i].length <= 16 - words[i] only consists of lowercase English letters.

---

🧒 Let's Build Understanding from Absolute Scratch

What Does "Predecessor" Even Mean?

Let me start with the DEFINITION:

wordA is a predecessor of wordB if:
  - We can insert EXACTLY ONE letter into wordA
  - Without changing order of other characters
  - To make it equal to wordB

Simple examples:

Is "a" a predecessor of "ba"?
  "a" → insert 'b' at front → "ba" ✓
  YES! ✓

Is "a" a predecessor of "ab"?
  "a" → insert 'b' at end → "ab" ✓
  YES! ✓

Is "ab" a predecessor of "abc"?
  "ab" → insert 'c' at end → "abc" ✓
  YES! ✓

Is "ab" a predecessor of "aXb"?
  "ab" → insert 'X' in middle → "aXb" ✓
  YES! ✓

Is "abc" a predecessor of "abcd"?
  "abc" → insert 'd' at end → "abcd" ✓
  YES! ✓

Is "abc" a predecessor of "abdc"?
  "abc" → insert 'd' between b and c → "abdc" ✓
  YES! ✓

Is "abc" a predecessor of "bac"?
  Can we get "bac" by inserting ONE letter into "abc"?
  NO! The order changed! ✗
  NO! ✗

KEY INSIGHT: 
  - wordB must be EXACTLY 1 character longer!
  - Characters must stay in SAME order!
  - We just INSERT one new character! 🔑

Understanding "Word Chain"

What's a word chain?

It's a sequence where each word is predecessor of next!

Example: ["a", "ba", "bda", "bdca"]

Check each link:
  "a" → "ba"?
    Insert 'b' at front ✓

  "ba" → "bda"?
    Insert 'd' in middle ✓

  "bda" → "bdca"?
    Insert 'c' between d and a ✓

All links work! This is a valid chain of length 4! ✓

Another example: ["a", "ab", "abc", "abcd"]

  "a" → "ab": insert 'b' ✓
  "ab" → "abc": insert 'c' ✓
  "abc" → "abcd": insert 'd' ✓

Valid chain of length 4! ✓

Invalid example: ["a", "ba", "abc"]

  "a" → "ba": insert 'b' ✓
  "ba" → "abc"?
    "ba" has length 2
    "abc" has length 3
    Insert one character: "ba" → "bXa" or "Xba" or "baX"
    Can we get "abc"? 
      "bac"? NO!
      "aba"? NO!
      "baa"? NO!
    NO! ✗

Not a valid chain! ✗

The problem: Find the LONGEST chain! 🔑

What Makes This Feel Like LIS?

Wait! This looks familiar!

LONGEST INCREASING SUBSEQUENCE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Array: [10, 9, 2, 5, 3, 7]

Question: Find longest chain where each > previous
Answer: [2, 3, 7] → length 3

Condition: nums[j] < nums[i]

LONGEST STRING CHAIN:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Words: ["a", "b", "ba", "bca", "bda", "bdca"]

Question: Find longest chain where each is predecessor of next
Answer: ["a", "ba", "bda", "bdca"] → length 4

Condition: wordA is predecessor of wordB

SAME PATTERN!
  - Looking for longest chain
  - Each element extends previous
  - Different condition!

LIS: nums[j] < nums[i]
This: isPredecessor(wordA, wordB)

It's LIS with a DIFFERENT comparison function! 🔑

First Intuition - How To Check Predecessor?

Given two words, how do I check if wordA is predecessor of wordB?

Requirements:
  1. wordB.length == wordA.length + 1 (exactly 1 longer)
  2. Removing ONE character from wordB gives wordA

Let me think about removing a character:

wordB = "abc"
Remove index 0: "bc"
Remove index 1: "ac"  
Remove index 2: "ab"

So for "abc", possible predecessors are: "bc", "ac", "ab"

If wordA is any of these, it's a predecessor! ✓

Example: Is "ab" predecessor of "abc"?
  wordB = "abc"
  Remove last character: "ab" ✓
  Matches wordA! ✓
  YES! ✓

Example: Is "ba" predecessor of "abc"?
  wordB = "abc"
  Possible by removing one: "bc", "ac", "ab"
  "ba" in this list? NO! ✗
  NO! ✗

Algorithm:
  For each position in wordB:
    Remove that character
    Check if result equals wordA
    If yes → wordA is predecessor! ✓

---

🤔 Building Intuition - The Complete Mental Model

Why Order Matters - Sorting Strategy

Unlike regular LIS with numbers where we sort numerically,
here we need to think: How should we sort STRINGS?

Key insight: If "a" → "ab" → "abc"
  Length: 1 → 2 → 3

Chains ALWAYS go from SHORTER to LONGER! 🔑

Why?
  Because we INSERT characters!
  Inserting makes words longer!

So: Sort by LENGTH! ✓

Example:
  words = ["abc", "a", "ab", "abcd"]

  After sorting by length:
    ["a", "ab", "abc", "abcd"]
     ↑    ↑     ↑      ↑
     len1 len2  len3   len4

Now we can build chains left to right! ✓

Working Through Simple Example

words = ["a", "b", "ba"]

STEP 1: Sort by length
  ["a", "b", "ba"]
  Already sorted! ✓

STEP 2: Apply LIS logic
  dp[i] = length of longest chain ending at word i

Initialize:
  dp = [1, 1, 1] (each word alone)

Process index 0 ("a"):
  No previous words
  dp[0] = 1

Process index 1 ("b"):
  Check index 0 ("a"):
    Is "a" predecessor of "b"?
    "b" has length 1, "a" has length 1
    NOT exactly 1 longer! ✗
    Can't extend!

  dp[1] = 1

Process index 2 ("ba"):
  Check index 0 ("a"):
    Is "a" predecessor of "ba"?
    "ba" length 2, "a" length 1 ✓ (exactly 1 longer)
    Remove from "ba": "b" or "a"
    "a" matches! ✓
    Can extend! dp[2] = dp[0] + 1 = 2

  Check index 1 ("b"):
    Is "b" predecessor of "ba"?
    "ba" length 2, "b" length 1 ✓
    Remove from "ba": "b" or "a"
    "b" matches! ✓
    Can extend! dp[2] = max(2, dp[1] + 1) = 2

Final: dp = [1, 1, 2]
Maximum: 2

Chains of length 2:
  ["a", "ba"] or ["b", "ba"]

Understanding The Predecessor Check

Let me trace isPredecessor("a", "ba") step by step:

wordA = "a" (length 1)
wordB = "ba" (length 2)

Step 1: Check lengths
  wordB.length == wordA.length + 1?
  2 == 1 + 1? YES! ✓

Step 2: Try removing each character from wordB

  Remove index 0 ('b'): "ba" → "a"
    Does "a" == wordA ("a")? YES! ✓
    Found it! Return true! ✓

So "a" IS predecessor of "ba"! ✓

Let me trace isPredecessor("ab", "abc"):

wordA = "ab" (length 2)
wordB = "abc" (length 3)

Step 1: Lengths
  3 == 2 + 1? YES! ✓

Step 2: Remove each character
  Remove index 0 ('a'): "abc" → "bc"
    "bc" == "ab"? NO!

  Remove index 1 ('b'): "abc" → "ac"
    "ac" == "ab"? NO!

  Remove index 2 ('c'): "abc" → "ab"
    "ab" == "ab"? YES! ✓
    Found it! ✓

So "ab" IS predecessor of "abc"! ✓

Complete Medium Example

words = ["a", "b", "ba", "bca", "bda", "bdca"]

STEP 1: Sort by length
  ["a", "b", "ba", "bca", "bda", "bdca"]
   len1 len1 len2  len3  len3  len4

STEP 2: Build DP

Initialize:
  dp = [1, 1, 1, 1, 1, 1]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 0: "a" (length 1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

No previous words.
dp[0] = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 1: "b" (length 1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check j=0 ("a"):
  Same length (1 == 1) ✗
  Can't be predecessor!

dp[1] = 1

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 2: "ba" (length 2)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check j=0 ("a"):
  2 == 1 + 1? YES! ✓
  Remove from "ba":
    "b" == "a"? NO
    "a" == "a"? YES! ✓
  Can extend!
  dp[2] = dp[0] + 1 = 2

Check j=1 ("b"):
  2 == 1 + 1? YES! ✓
  Remove from "ba":
    "b" == "b"? YES! ✓
  Can extend!
  dp[2] = max(2, dp[1] + 1) = 2

dp[2] = 2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 3: "bca" (length 3)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check j=0 ("a"): length 1, not 2 ✗
Check j=1 ("b"): length 1, not 2 ✗

Check j=2 ("ba"):
  3 == 2 + 1? YES! ✓
  Remove from "bca":
    "ca" == "ba"? NO
    "ba" == "ba"? YES! ✓
  Can extend!
  dp[3] = dp[2] + 1 = 3

dp[3] = 3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 4: "bda" (length 3)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check j=0 ("a"): length 1, not 2 ✗
Check j=1 ("b"): length 1, not 2 ✗

Check j=2 ("ba"):
  3 == 2 + 1? YES! ✓
  Remove from "bda":
    "da" == "ba"? NO
    "ba" == "ba"? YES! ✓
  Can extend!
  dp[4] = dp[2] + 1 = 3

Check j=3 ("bca"):
  Same length (3 == 3) ✗

dp[4] = 3

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INDEX 5: "bdca" (length 4)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Check j=0,1,2: lengths 1,1,2, not 3 ✗

Check j=3 ("bca"):
  4 == 3 + 1? YES! ✓
  Remove from "bdca":
    "dca" == "bca"? NO
    "bca" == "bca"? YES! ✓
  Can extend!
  dp[5] = dp[3] + 1 = 4

Check j=4 ("bda"):
  4 == 3 + 1? YES! ✓
  Remove from "bdca":
    "dca" == "bda"? NO
    "bca" == "bda"? NO
    "bda" == "bda"? YES! ✓
  Can extend!
  dp[5] = max(4, dp[4] + 1) = 4

dp[5] = 4

Final: dp = [1, 1, 2, 3, 3, 4]
Maximum: 4 ✓

The chain: ["a", "ba", "bda", "bdca"]
  or: ["a", "ba", "bca", "bdca"]

---

---

🔴 Approach 1: Brute Force - Explore All Possible Chains (DFS)

The Recursive Idea

To find the longest chain, we need to try ALL possibilities:
  1. Start a chain from each word
  2. From current word, try extending to EVERY longer word
  3. Recursively explore each valid extension
  4. Track the maximum chain length found

This is NOT greedy - it explores EVERY possible path! ✓

Complete DFS Implementation

class Solution {
    private int maxLen = 0;

    public int longestStrChain(String[] words) {
        // Sort by length first
        Arrays.sort(words, (a, b) -> a.length() - b.length());

        // Try starting a chain from each word
        for (int i = 0; i < words.length; i++) {
            dfs(words, i, 1);
        }

        return maxLen;
    }

    private void dfs(String[] words, int currentIndex, int chainLength) {
        // Update maximum length found
        maxLen = Math.max(maxLen, chainLength);

        // Try extending to each word that comes after current
        for (int i = currentIndex + 1; i < words.length; i++) {
            if (isPredecessor(words[currentIndex], words[i])) {
                // Recursively explore this extension
                dfs(words, i, chainLength + 1);
            }
        }
        // When no more extensions possible, recursion returns
    }

    private boolean isPredecessor(String wordA, String wordB) {
        if (wordB.length() != wordA.length() + 1) {
            return false;
        }

        for (int i = 0; i < wordB.length(); i++) {
            String removed = wordB.substring(0, i) + wordB.substring(i + 1);
            if (removed.equals(wordA)) {
                return true;
            }
        }

        return false;
    }
}

Trace Through Your Test Case

words = ["a", "ab", "ac", "bd", "abc", "abd", "abdd"]
After sort: same order

Starting from i=0 ("a"):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  dfs("a", index=0, len=1)
    maxLen = 1

    Try extending to i=1 ("ab"):
      isPredecessor("a", "ab")? YES! ✓

      dfs("ab", index=1, len=2)
        maxLen = 2

        Try extending to i=4 ("abc"):
          isPredecessor("ab", "abc")? YES! ✓

          dfs("abc", index=4, len=3)
            maxLen = 3
            Try i=5,6: no extensions
            Return

        Try extending to i=5 ("abd"):
          isPredecessor("ab", "abd")? YES! ✓

          dfs("abd", index=5, len=3)
            maxLen = 3

            Try extending to i=6 ("abdd"):
              isPredecessor("abd", "abdd")? YES! ✓

              dfs("abdd", index=6, len=4)
                maxLen = 4 ✓✓✓ FOUND!
                No more words to extend
                Return

            Return

        Return

    Try extending to i=2 ("ac"):
      ... explores this path too ...

    Return

... continues from other starting points ...

Final: maxLen = 4 ✓

The chain ["a", "ab", "abd", "abdd"] is discovered! ✓

Understanding Why DFS Works

DFS is different from greedy!

GREEDY (wrong):
  At each step, take FIRST valid extension
  Example: "ab" → sees "abc" first → takes it
  Blocked from optimal path! ✗

DFS (correct):
  At each step, try ALL valid extensions
  Example: "ab" → tries BOTH "abc" AND "abd"
  Explores both paths:
    Path 1: "a" → "ab" → "abc" (length 3)
    Path 2: "a" → "ab" → "abd" → "abdd" (length 4) ✓
  Finds optimal! ✓

DFS explores the ENTIRE search space! 🔑

Why This Is Too Slow

This approach CORRECTLY finds the answer! ✓

BUT it's SLOW! ✗

TIME COMPLEXITY:

Consider worst case: all words form valid chains

Example: ["a", "ab", "abc", "abcd", ...]

From "a", we try extending to all n-1 words
  From "ab", we try extending to all remaining
    From "abc", we try extending to all remaining
      ... and so on

This creates an exponential search tree!

For each isPredecessor call: O(L)

Total: O(2^n × L) worst case ❌

For n = 1000:
  2^1000 possibilities - IMPOSSIBLE! ❌

SPACE COMPLEXITY:
  Recursion stack: O(n) in worst case
  (if chain includes all words)

Verdict: 
  ✓ CORRECT - explores all possibilities
  ✗ TOO SLOW - exponential time

We need to avoid recalculating subproblems!
→ Dynamic Programming! ✓

---

🟢 Approach 2: Dynamic Programming - Avoiding Repeated Work

The Key Insight - Overlapping Subproblems

In DFS, we recalculate the same thing multiple times!

Example:
  Path 1: "a" → "ab" → "abd"
           Need: longest chain ending at "ab"

  Path 2: Start from "ab" → "abd"
           Need: longest chain ending at "ab" (SAME!)

DFS recalculates! ✗
DP stores once, reuses! ✓

This is why DP is faster! 🔑

The DP Solution - Array Approach

Key insight from LIS pattern:
  dp[i] = longest chain ending at word i

For each word i:
  Check ALL previous words j < i
  If words[j] is predecessor of words[i]:
    dp[i] = max(dp[i], dp[j] + 1)

Same structure as LIS! ✓

Complete Implementation

class Solution {
    public int longestStrChain(String[] words) {
        // STEP 1: Sort by length (shorter words first)
        Arrays.sort(words, (a, b) -> a.length() - b.length());

        int n = words.length;

        // STEP 2: DP array
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // Each word alone is chain of length 1

        int maxChain = 1;

        // STEP 3: Fill DP array
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // Can we extend chain ending at j with word i?
                if (isPredecessor(words[j], words[i])) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxChain = Math.max(maxChain, dp[i]);
        }

        return maxChain;
    }

    private boolean isPredecessor(String wordA, String wordB) {
        // wordA must be exactly 1 character shorter
        if (wordB.length() != wordA.length() + 1) {
            return false;
        }

        // Try removing each character from wordB
        for (int i = 0; i < wordB.length(); i++) {
            // Create string with i-th character removed
            String removed = wordB.substring(0, i) + wordB.substring(i + 1);

            if (removed.equals(wordA)) {
                return true;
            }
        }

        return false;
    }
}

Understanding isPredecessor In Detail

private boolean isPredecessor(String wordA, String wordB) {
    // Example: wordA = "ab", wordB = "abc"

    // Check: "abc".length() == "ab".length() + 1?
    //        3 == 2 + 1? YES! ✓
    if (wordB.length() != wordA.length() + 1) {
        return false;
    }

    // Try removing each position from "abc"
    for (int i = 0; i < wordB.length(); i++) {
        // i=0: remove 'a' → "bc"
        //      "bc" == "ab"? NO

        // i=1: remove 'b' → "ac"
        //      "ac" == "ab"? NO

        // i=2: remove 'c' → "ab"
        //      "ab" == "ab"? YES! ✓
        //      Return true!

        String removed = wordB.substring(0, i) + wordB.substring(i + 1);

        if (removed.equals(wordA)) {
            return true;
        }
    }

    return false;
}

Why This Works

Example: words = ["a", "ab", "abd", "abdd"]

After sort: ["a", "ab", "abd", "abdd"]

Initialize:
  dp = [1, 1, 1, 1]

Process "a" (i=0):
  No previous words
  dp[0] = 1

Process "ab" (i=1):
  Check j=0 ("a"):
    isPredecessor("a", "ab")? YES! ✓
    dp[1] = max(1, dp[0] + 1) = 2

Process "abd" (i=2):
  Check j=0 ("a"):
    isPredecessor("a", "abd")? NO (length 1 vs 3)
  Check j=1 ("ab"):
    isPredecessor("ab", "abd")? YES! ✓
    dp[2] = max(1, dp[1] + 1) = 3

Process "abdd" (i=3):
  Check j=0 ("a"): NO (length mismatch)
  Check j=1 ("ab"): NO (length 2 vs 4)
  Check j=2 ("abd"):
    isPredecessor("abd", "abdd")? YES! ✓
    dp[3] = max(1, dp[2] + 1) = 4

Final: dp = [1, 2, 3, 4]
maxChain = 4 ✓

The chain: ["a", "ab", "abd", "abdd"]

DP considers ALL possibilities! ✓

---

🟡 Approach 3: Optimization - Discovering The HashMap Idea

Let's Think About The Array DP Problem

In Approach 2, for each word at position i:
  We check ALL j < i to see if words[j] is a predecessor

Example: words = ["a", "b", "ba", "bca", "bda", "bdca"]
After sort: same order

When processing "bdca" (index 5):
  Check "a": is "a" predecessor of "bdca"? 
    Length 1 vs 4 → NO
  Check "b": is "b" predecessor of "bdca"?
    Length 1 vs 4 → NO
  Check "ba": is "ba" predecessor of "bdca"?
    Length 2 vs 4 → NO
  Check "bca": is "bca" predecessor of "bdca"?
    Length 3 vs 4 → YES! Check if predecessor...
  Check "bda": is "bda" predecessor of "bdca"?
    Length 3 vs 4 → YES! Check if predecessor...

We checked 5 words! But only 2 could possibly work! ✗

Can we do better? 🤔

The Key Observation - Reversing The Question

Instead of asking:
  "Is words[j] a predecessor of words[i]?"
  → Check many words ✗

What if we ask:
  "What ARE the predecessors of words[i]?"
  → Generate just the valid ones! ✓

Let me think about "bdca":

  If something is a predecessor, it means:
    I can insert ONE character into it to get "bdca"

  Reverse thinking:
    Remove ONE character from "bdca" to get predecessor!

  What can I remove from "bdca"?
    Remove 'b': "dca"
    Remove 'd': "bca" ✓ (this might exist!)
    Remove 'c': "bda" ✓ (this might exist!)
    Remove 'a': "bdc"

Only 4 possibilities! Not 5+ words to check! 🔑

Now the question becomes:
  Do any of ["dca", "bca", "bda", "bdc"] exist in our word list?

If I had a FAST way to check existence... like a HashMap! ✓

Building The Intuition Step By Step

Let me work through an example manually:

words = ["a", "ba", "bda"]

The OLD way (Array DP):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Process "a":
  No previous words
  dp[0] = 1

Process "ba":
  Check j=0: is "a" predecessor? YES!
  dp[1] = dp[0] + 1 = 2

Process "bda":
  Check j=0: is "a" predecessor? NO (length mismatch)
  Check j=1: is "ba" predecessor? YES!
  dp[2] = dp[1] + 1 = 3

Total checks: 3


The NEW way (Generate predecessors):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Process "a":
  What are predecessors of "a"?
    Remove index 0: "" (empty)

  Does "" exist? NO
  So longest = 0
  dp["a"] = 0 + 1 = 1

Process "ba":
  What are predecessors of "ba"?
    Remove index 0: "a"
    Remove index 1: "b"

  Does "a" exist? YES! dp["a"] = 1
  Does "b" exist? NO

  So longest = 1
  dp["ba"] = 1 + 1 = 2

Process "bda":
  What are predecessors of "bda"?
    Remove index 0: "da"
    Remove index 1: "ba"
    Remove index 2: "bd"

  Does "da" exist? NO
  Does "ba" exist? YES! dp["ba"] = 2
  Does "bd" exist? NO

  So longest = 2
  dp["bda"] = 2 + 1 = 3

Total checks: 6 (but against HashMap, not array!)

Same answer! ✓

Why HashMap Is Better - The Math

Let's compare:

Array DP Approach:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

For word at position i:
  - Must check ALL j < i words
  - In worst case: i words to check
  - Average: n/2 words to check

  For each check: O(L) to verify predecessor

  Total per word: O(n × L)
  Total for all: O(n² × L)


Generate Predecessors Approach:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

For word of length L:
  - Generate L predecessors (remove each position)
  - Each generation: O(L) to create string
  - Check existence in HashMap: O(L) to hash string

  Total per word: O(L × L) = O(L²)
  Total for all: O(n × L²)

COMPARISON:

When is O(n × L²) better than O(n² × L)?
  Divide both by n × L:
    O(L) vs O(n)

  When L < n, second is better!

For this problem:
  L ≤ 16 (max word length)
  n ≤ 1000 (max words)

  16 < 1000! ✓

HashMap approach is better! 🚀

Discovering The Algorithm Naturally

So the algorithm becomes:

1. Still need to sort by length (shorter first)
   Why? To process shorter words before longer ones!

2. Use HashMap instead of array
   Key: the word itself
   Value: longest chain ending at this word

3. For each word:
   a) Generate ALL possible predecessors
      (remove each character position)

   b) Check if each predecessor exists in HashMap

   c) Take the MAXIMUM chain length found

   d) Store current word with (max + 1)

Let me trace this completely!

Complete Trace With HashMap

words = ["a", "ba", "bda", "bdca"]
After sort: same

HashMap = {} (empty initially)
maxChain = 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS: "a"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Generate predecessors by removing each position:
  Position 0: "a"[0..0] + "a"[1..] = "" + "" = ""

Check HashMap:
  Does "" exist? NO
  longest = 0

Store result:
  HashMap["a"] = 0 + 1 = 1
  maxChain = max(0, 1) = 1

State: HashMap = {"a": 1}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS: "ba"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Generate predecessors:
  Position 0: "ba"[0..0] + "ba"[1..] = "" + "a" = "a"
  Position 1: "ba"[0..1] + "ba"[2..] = "b" + "" = "b"

Check HashMap:
  Does "a" exist? YES! HashMap["a"] = 1 ✓
  Does "b" exist? NO

  longest = max(1, 0) = 1

Store result:
  HashMap["ba"] = 1 + 1 = 2
  maxChain = max(1, 2) = 2

State: HashMap = {"a": 1, "ba": 2}

Why this works:
  "a" is predecessor of "ba"
  "a" has chain length 1
  So "ba" has chain length 2! ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS: "bda"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Generate predecessors:
  Position 0: "bda"[0..0] + "bda"[1..] = "" + "da" = "da"
  Position 1: "bda"[0..1] + "bda"[2..] = "b" + "a" = "ba"
  Position 2: "bda"[0..2] + "bda"[3..] = "bd" + "" = "bd"

Check HashMap:
  Does "da" exist? NO
  Does "ba" exist? YES! HashMap["ba"] = 2 ✓
  Does "bd" exist? NO

  longest = max(0, 2, 0) = 2

Store result:
  HashMap["bda"] = 2 + 1 = 3
  maxChain = max(2, 3) = 3

State: HashMap = {"a": 1, "ba": 2, "bda": 3}

Why this works:
  "ba" is predecessor of "bda"
  "ba" has chain length 2
  So "bda" has chain length 3! ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS: "bdca"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Generate predecessors:
  Position 0: "" + "dca" = "dca"
  Position 1: "b" + "ca" = "bca"
  Position 2: "bd" + "a" = "bda"
  Position 3: "bdc" + "" = "bdc"

Check HashMap:
  Does "dca" exist? NO
  Does "bca" exist? NO
  Does "bda" exist? YES! HashMap["bda"] = 3 ✓
  Does "bdc" exist? NO

  longest = max(0, 0, 3, 0) = 3

Store result:
  HashMap["bdca"] = 3 + 1 = 4
  maxChain = max(3, 4) = 4

State: HashMap = {"a": 1, "ba": 2, "bda": 3, "bdca": 4}

Why this works:
  "bda" is predecessor of "bdca"
  "bda" has chain length 3
  So "bdca" has chain length 4! ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

FINAL ANSWER: maxChain = 4 ✓

The chain: "a" → "ba" → "bda" → "bdca"

The "Aha!" Moment

Array DP says:
  "Let me check if ANY of these words is my predecessor"
  → Check many words ✗

HashMap DP says:
  "Let me generate MY predecessors and see if they exist"
  → Generate few, check fast! ✓

It's like:

ARRAY DP (slow):
  Me: "Is anyone here my parent?"
  Check 1000 people one by one... ✗

HASHMAP DP (fast):
  Me: "My parent's name is one of these 5 names"
  Look up in phone book... ✓

Different question → Different efficiency! 🔑

Now The Code Makes Perfect Sense

public int longestStrChain(String[] words) {
    // Sort by length (process shorter first)
    Arrays.sort(words, (a, b) -> a.length() - b.length());

    // HashMap: word → longest chain ending at this word
    Map<String, Integer> dp = new HashMap<>();

    int maxChain = 1;

    for (String word : words) {
        int longest = 0;

        // Generate ALL possible predecessors
        for (int i = 0; i < word.length(); i++) {
            // Remove character at position i
            String predecessor = word.substring(0, i) + word.substring(i + 1);

            // Check if this predecessor exists
            // If yes, get its chain length
            longest = Math.max(longest, dp.getOrDefault(predecessor, 0));
        }

        // Current word extends the best predecessor found
        dp.put(word, longest + 1);
        maxChain = Math.max(maxChain, longest + 1);
    }

    return maxChain;
}

Every line now makes sense! ✓

### Understanding getOrDefault

What does dp.getOrDefault(predecessor, 0) do?

It says: "Give me the value for this key If key doesn't exist, give me 0 instead"

Why 0? If predecessor doesn't exist in HashMap: It means we never processed it So its chain length is 0 Adding 1 gives us chain length 1 (just current word)

Example: word = "ba" predecessor = "b"

If "b" not in HashMap: dp.getOrDefault("b", 0) returns 0 longest = 0 dp["ba"] = 0 + 1 = 1 ✓

If "b" exists with dp["b"] = 2: dp.getOrDefault("b", 0) returns 2 longest = 2 dp["ba"] = 2 + 1 = 3 ✓

It handles both cases elegantly! ✓

---

## 🔍 Complex Example

### Example: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]

STEP 1: Sort by length ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"] len2 len3 len4 len5 len6

STEP 2: Process with HashMap

Process "xb" (length 2): Predecessors: "b", "x" None exist in dp dp["xb"] = 1

Process "xbc" (length 3): Predecessors: "bc", "xc", "xb" dp["xb"] = 1 ✓ dp["xbc"] = 2

Process "cxbc" (length 4): Predecessors: "xbc", "cbc", "cxc", "cxb" dp["xbc"] = 2 ✓ dp["cxbc"] = 3

Process "pcxbc" (length 5): Predecessors: "cxbc", "pxbc", "pcbc", "pcxc", "pcxb" dp["cxbc"] = 3 ✓ dp["pcxbc"] = 4

Process "pcxbcf" (length 6): Predecessors: "cxbcf", "pxbcf", "pcbcf", "pcxcf", "pcxbf", "pcxbc" dp["pcxbc"] = 4 ✓ dp["pcxbcf"] = 5

Answer: 5 ✓

The chain: ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"]

---

## 📊 Complexity Analysis

### All Approaches Compared

┌──────────────────┬─────────────┬──────────────┬──────────────┐ │ Approach │ Time │ Space │ Practical? │ ├──────────────────┼─────────────┼──────────────┼──────────────┤ │ DFS Brute Force │ O(2^n×L) │ O(n) │ NO ❌ │ │ (Approach 1) │ Exponential │ Stack │ Too slow │ ├──────────────────┼─────────────┼──────────────┼──────────────┤ │ Array DP │ O(n²×L) │ O(n) │ YES ✓ │ │ (Approach 2) │ Quadratic │ Array │ Good │ ├──────────────────┼─────────────┼──────────────┼──────────────┤ │ HashMap DP │ O(n×L²) │ O(n×L) │ YES ✓ │ │ (Approach 3) │ Linear │ HashMap │ Best! │ └──────────────────┴─────────────┴──────────────┴──────────────┘

n = number of words L = maximum word length (≤ 16)

### Detailed Time Complexity

APPROACH 1: DFS Brute Force ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Sorting: O(n log n × L) DFS: Try starting from each word: n iterations At each level, try extending to remaining words Creates exponential search tree

For each isPredecessor: O(L)

Total: O(2^n × L) ❌

For n = 50: 2^50 = way too slow! ❌

APPROACH 2: Array DP ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Sorting: O(n log n × L) for string comparison DP: Outer loop: n iterations Inner loop: up to n iterations isPredecessor: O(L) for each check

Total: O(n log n × L) + O(n² × L) = O(n² × L)

For n=1000, L=16: 16,000,000 operations ✓

APPROACH 3: HashMap DP ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Sorting: O(n log n × L) DP: For each word: n iterations Generate predecessors: L iterations String operations: O(L) per predecessor HashMap lookup: O(L) for string hashing

Total: O(n log n × L) + O(n × L × L) = O(n × L²)

For n=1000, L=16: 256,000 operations ✓

62x faster than Approach 2! 🚀

### Space Complexity

APPROACH 1: Recursion stack: O(n) Total: O(n)

APPROACH 2: dp array: O(n) Total: O(n)

APPROACH 3: HashMap: O(n) entries Each entry: word (O(L)) + count (O(1)) Total: O(n × L)

Slightly more space but negligible! ✓

---

## 💻 Complete Working Code

```java
class Solution {
  // APPROACH 2: Array DP
  public int longestStrChain_ArrayDP(String[] words) {
    Arrays.sort(words, (a, b) -> a.length() - b.length());

    int n = words.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int maxChain = 1;

    for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
        if (isPredecessor(words[j], words[i])) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      maxChain = Math.max(maxChain, dp[i]);
    }

    return maxChain;
  }

  private boolean isPredecessor(String wordA, String wordB) {
    if (wordB.length() != wordA.length() + 1) {
      return false;
    }

    for (int i = 0; i < wordB.length(); i++) {
      String removed = wordB.substring(0, i) + wordB.substring(i + 1);
      if (removed.equals(wordA)) {
        return true;
      }
    }

    return false;
  }

  // APPROACH 3: HashMap DP (OPTIMAL!)
  public int longestStrChain(String[] words) {
    Arrays.sort(words, (a, b) -> a.length() - b.length());

    Map<String, Integer> dp = new HashMap<>();
    int maxChain = 1;

    for (String word : words) {
      int longest = 0;

      // Generate all possible predecessors
      for (int i = 0; i < word.length(); i++) {
        String prev = word.substring(0, i) + word.substring(i + 1);
        longest = Math.max(longest, dp.getOrDefault(prev, 0));
      }

      dp.put(word, longest + 1);
      maxChain = Math.max(maxChain, longest + 1);
    }

    return maxChain;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    System.out.println(sol.longestStrChain(new String[] {"a", "b", "ba", "bca", "bda", "bdca"})); // 4
    System.out.println(sol.longestStrChain(new String[] {"xbc", "pcxbcf", "xb", "cxbc", "pcxbc"})); // 5
    System.out.println(sol.longestStrChain(new String[] {"abcd", "dbqca"})); // 1
    System.out.println(sol.longestStrChain(new String[] {"a", "ab", "abd", "abdd"})); // 4
  }
}

---

🔑 Key Insights Summary

The Learning Journey

CRAWL (Understanding):
  ✓ What is a predecessor? (insert exactly 1 char)
  ✓ What is a word chain?
  ✓ Connection to LIS pattern
  ✓ Why sort by length?

WALK (Building):
  ✓ How to check isPredecessor
  ✓ Simple example traced completely
  ✓ Medium example with all indices
  ✓ Understanding DP state

RUN (Mastery):
  ✓ Array DP solution
  ✓ HashMap optimization
  ✓ Why HashMap is faster
  ✓ Complex example traced
  ✓ Complete implementations

Natural baby-to-expert progression! 🎯

The Core Understanding

1. WHY sort by length?
   Chains go SHORT → LONG
   Inserting makes words longer!

2. WHAT makes this LIS?
   Same structure: longest chain
   Different condition: predecessor vs <

3. HOW to check predecessor?
   wordB exactly 1 longer
   Remove each char from wordB
   Check if any equals wordA

4. WHEN is HashMap better?
   Generate predecessors instead of check all
   O(L) predecessors vs O(n) previous words
   When L << n: HashMap wins!

5. WHERE's the optimization?
   Array: Check ALL previous O(n)
   HashMap: Generate L predecessors, check existence O(1)
   Key insight! 🔑

Mental Model

Think of building chains like stacking blocks:

Foundation: Shortest words
  "a", "b"

First level: Add 1 character
  "ab", "ba"

Second level: Add 1 more
  "abc", "bda"

Third level: Keep building
  "abcd", "bdca"

Each level MUST come from previous level!
Sort by length ensures we build bottom-up! ✓

---

📝 Quick Revision

🎯 Core Concept

LIS variant on strings
Predecessor = insert exactly 1 character
Sort by length first (SHORT → LONG)

⚡ Algorithm (HashMap - Optimal)

Sort words by length

For each word:
  longest = 0

  For each position i in word:
    predecessor = remove char at i
    longest = max(longest, dp[predecessor])

  dp[word] = longest + 1
  maxChain = max(maxChain, longest + 1)

Return maxChain

🔑 Quick Implementation

import java.util.Arrays;
import java.util.HashMap;

public class Solution {
  int maxLen = 0;

  public int longestStrChain(String[] words) {
    maxLen = 0;
    // return dfs(words); // bruteforce

    // This is enough. No need of hashing I feel
    // return bottomUp(words);

    return hashing(words);
  }

  private int hashing(String[] words) {
    // step 0: sort the words in the ascending order of their increasing lengths
    Arrays.sort(words, (a, b) -> a.length() - b.length());

    int len = words.length;
    // step 1: same as earlier DP LIS problems
    // instead of array earlier, use hashmap now
    HashMap<String, Integer> map = new HashMap<>();

    int res = 1;

    // step 2: same as earlier DP LIS problems except with some condition
    for (int i = 0; i < len; i++) {
      String curr = words[i];
      int currChainLen = 0;

      // step 2: remove every character from curr and check if its in hashmap.
      // if its hashmap, update the chain length.
      for (int j = 0; j < curr.length(); j++) {
        String removed = curr.substring(0, j) + curr.substring(j + 1);

        if (map.containsKey(removed)) {
          currChainLen = Math.max(currChainLen, map.get(removed));
        }
      }

      // Step 3: We stores every words[i] in hashmap with the result.
      map.put(curr, currChainLen + 1);

      // step 4: update res
      res = Math.max(currChainLen + 1, res);
    }

    return res;
  }

  private int bottomUp(String[] words) {
    // step 0: sort the words in the ascending order of their increasing lengths
    Arrays.sort(words, (a, b) -> a.length() - b.length());

    int len = words.length;
    int[] dp = new int[len];
    // step 1: same as earlier DP LIS problems
    Arrays.fill(dp, 1);

    int res = 1;

    // step 2: same as earlier DP LIS problems except with some condition
    for (int i = 1; i < len; i++) {
      for (int j = 0; j < i; j++) {
        if (isPredecessor(words[j], words[i])) {
          dp[i] = Math.max(dp[i], 1 + dp[j]);
        }
      }

      res = Math.max(res, dp[i]);
    }

    return res;
  }

  private int dfs(String[] words) {
    // step 0: sort the words in the ascending order of their increasing lengths
    Arrays.sort(words, (a, b) -> a.length() - b.length());

    // Step 1: Do DFS start from every node
    for (int i = 0; i < words.length; i++) {
      dfsUtil(words, i, 1);
    }

    return maxLen;
  }

  private void dfsUtil(String[] words, int curr, int currChainLen) {
    // step 3: update maxlen
    maxLen = Math.max(currChainLen, maxLen);

    // step 4: base case
    if (curr == words.length) {
      return;
    }

    // step 2: start from next node and keep on doing.
    // while calling, increase the length of the current chain.
    for (int i = curr + 1; i < words.length; i++) {
      if (isPredecessor(words[curr], words[i])) {
        dfsUtil(words, i, currChainLen + 1);
      }
    }
  }

  private boolean isPredecessor(String wordA, String wordB) {
    // check if s1 is a predecessor of s2.
    // Means remove every character of s2 and compare if its equal to s1.
    if (wordA.length() + 1 != wordB.length()) {
      return false;
    }

    for (int i = 0; i < wordB.length(); i++) {
      String removed = wordB.substring(0, i) + wordB.substring(i + 1);

      if (removed.equals(wordA)) {
        return true;
      }
    }

    return false;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.longestStrChain(new String[] { "a", "b", "ba", "bca", "bda", "bdca" }) == 4);
    System.out.println(s.longestStrChain(new String[] { "xbc", "pcxbcf", "xb",
        "cxbc", "pcxbc" }) == 5);
    System.out.println(s.longestStrChain(new String[] { "abcd", "dbqca" }) == 1);
    System.out.println(s.longestStrChain(new String[] { "a", "ab", "ac", "bd", "abc", "abd", "abdd" }) == 4);
  }
}

🔑 Key Patterns

Predecessor check:
  - wordB.length == wordA.length + 1
  - Remove each char from wordB
  - Check if any equals wordA

HashMap optimization:
  - Generate predecessors (O(L))
  - Check existence (O(1))
  - Faster than checking all previous (O(n))

🎪 Memory Aid

"Sort short to long"
"Remove one, check match"
"HashMap beats array when L << n"

Complexity: O(n × L²) time, O(n) space

---

🎉 Congratulations!

You've mastered through baby steps: - ✅ CRAWL: Understanding predecessor concept - ✅ WALK: Building DP solution - ✅ RUN: HashMap optimization - ✅ WHY sort by length - ✅ HOW to check predecessor efficiently - ✅ Complete examples traced - ✅ Two complete implementations - ✅ True comprehensive understanding

You've learned LIS on strings with optimization using true textbook-style baby-to-expert learning! 🚀✨

KEY TAKEAWAY: When checking relationships between elements is expensive (O(L)), consider GENERATING candidates instead and using HashMap for O(1) lookup! This transforms O(n²×L) to O(n×L²)! 🔑