DP 45: Longest String Chain | Longest Increasing Subsequence (LIS)

1. Introduction and Problem Definition

The Longest String Chain problem is a classic algorithmic challenge that directly extends the concepts of the Longest Increasing Subsequence (LIS).

What is a String Chain?

Given an array of strings (words), a string chain is formed by sequencing words such that each subsequent word is created by inserting exactly one character into the previous word at any arbitrary position.

• Example Chain: a -> ba -> bca -> bdca
  • From a, insert b anywhere -> ba
  • From ba, insert c anywhere -> bca
  • From bca, insert d anywhere -> bdca

The objective is to find the maximum length possible among all valid string chains that can be formed from the given array.

2. Prerequisites and Core Mental Model

Before tackling this chapter, you must be thoroughly familiar with DP 41 and DP 42 (Longest Increasing Subsequence).

Real-Life Analogy: The Word Building Blocks

Think of each word as a building block of a specific length. You are trying to build the tallest possible tower. However, you can only stack a block on top of another block if the upper block is an exact copy of the lower block plus one extra brick (character) inserted somewhere inside. You want to find the maximum height (length) of the tower you can construct.

3. Connecting LIS to String Chains

In a standard LIS problem, we deal with an array of numbers (e.g., [1, 4, 3, 7, 10]) and look for an increasing sequence where each element is strictly greater than the previous one:

arr[i] > arr[j]

In the Longest String Chain problem:

• The structure matches LIS: we look for a subsequence/subset where elements transition sequentially.
• The condition changes: instead of checking if a number is greater than another, we check if string arr[i] can be formed by inserting exactly one character into string arr[j].

4. Naive vs. Better Approach: The Sorting Crucial Fix

The Initial Flaw (Subsequence vs. Subset)

Initially, we might think this is a pure subsequence problem where order in the original array matters. However, strings can appear in any order in the input array. For example, if we have strings like xb, xbc, xbcf, the valid chain can be formed regardless of their original indices as long as we evaluate them in order of their lengths.

The Solution: Sorting by Length

To fix this, we must sort the array of strings by their lengths in ascending order. Once sorted:

1. Shorter strings naturally appear before longer strings.
2. We can safely apply the LIS tabular/DP evaluation knowing that any potential predecessor will always appear at a preceding index.

5. Step-by-Step Evolution of the Check Function

To determine if string s1 (the longer string) can be formed by inserting a character into string s2 (the shorter string), we need a helper function: checkPossible(string &s1, string &s2).

Rules for the Check Function:

1. Length Validation: The length of s1 must be exactly equal to s2.size() + 1. If not, return false.
2. Two-Pointer Traversal: Use two pointers (first for s1, second for s2) to scan both strings:
   • If characters match (s1[first] == s2[second]), advance both pointers.
   • If characters do not match, advance only the pointer on the longer string (s1), representing the single inserted character.
   • At the end of traversal, if both pointers have reached the end of their respective strings simultaneously, the transition is valid.

Visual Flow of the Check Function

6. Complete Code Implementation (C++)

Below is the complete, optimized C++ solution incorporating length-based sorting and the custom string comparison function:

class Solution {
private:
    // Helper function to check if s1 can be formed by inserting 1 char into s2
    bool checkPossible(string &s1, string &s2) {
        if (s1.size() != s2.size() + 1) return false;
        
        int first = 0;
        int second = 0;
        
        while (first < s1.size()) {
            if (second < s2.size() && s1[first] == s2[second]) {
                first++;
                second++;
            } else {
                first++;
            }
        }
        
        // If both pointers have traversed their respective strings completely
        if (first == s1.size() && second == s2.size()) {
            return true;
        }
        return false;
    }

    // Custom comparator to sort strings by their lengths
    static bool compare(const string &s1, const string &s2) {
        return s1.size() < s2.size();
    }

public:
    int longestStrChain(vector<string>& words) {
        int n = words.size();
        
        // Step 1: Sort words based on length
        sort(words.begin(), words.end(), compare);
        
        // Step 2: Initialize DP array for LIS
        vector<int> dp(n, 1);
        int maxi = 1;
        
        // Step 3: Apply LIS logic with custom checkPossible condition
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (checkPossible(words[i], words[j]) && 1 + dp[j] > dp[i]) {
                    dp[i] = 1 + dp[j];
                }
            }
            maxi = max(maxi, dp[i]);
        }
        
        return maxi;
    }
};

7. Complexity Analysis

8. Summary and Key Takeaways

• Problem Mapping: Longest String Chain is a structural variant of the Longest Increasing Subsequence (LIS) problem, replacing numerical greater-than checks with a single-character insertion check.
• Prerequisite Ordering: Because chains can be formed regardless of input order, sorting the array by string length beforehand is mandatory.
• Length Constraint Check: Before comparing characters, always verify that s1.size() == s2.size() + 1.
• Two-Pointer Scanning: Use two independent pointers (first and second) to verify if the longer string can be reduced to the shorter string by skipping exactly one character.
• DP State Transition: dp[i] = max(dp[i], 1 + dp[j]) whenever checkPossible(words[i], words[j]) evaluates to true.
• Robust Scalability: This pattern demonstrates how dynamic programming templates can be adapted to non-numeric domains (like strings, objects, or intervals) by swapping out the comparator logic.