> For the complete documentation index, see [llms.txt](https://code-render.gitbook.io/leetcode-editorials/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-render.gitbook.io/leetcode-editorials/09-september/23-longest-string-chain.md).

# 23- Longest String Chain

The problem can be found at the following link: [Question Link](https://leetcode.com/problems/longest-string-chain/description/)

## My Approach

1. Custom Comparison Function `cmp`:
   * Define a static bool function `cmp` that takes two string parameters, `a` and `b`.
   * It compares two strings based on their lengths, returning `true` if the length of `a` is less than the length of `b`, and `false` otherwise.
2. `isSubsequence` Function:
   * Define a member function `isSubsequence` that takes two string parameters, `s` and `t`.
   * Initialize an integer variable `j` to 0. This variable will be used to iterate through the characters of `s`.
   * Iterate through the characters of string `t` using a for loop.
   * Inside the loop, check if the current character in `t` at index `i` is equal to the current character in `s` at index `j`.
   * If they are equal, increment the `j` variable.
   * After the loop, check if the length of `s` is equal to `j`. If it is, return `true`, indicating that `s` is a subsequence of `t`. Otherwise, return `false`.
3. `longestStrChain` Function:
   * Define a member function `longestStrChain` that takes a reference to a vector of strings, `words`.
   * Sort the `words` vector using the custom comparison function `cmp`. This sorting is done in ascending order of string lengths.
   * Initialize an integer variable `n` to store the number of words in the input vector `words`.
   * Create a dynamic programming (DP) vector `dp` of size `n`, where each element represents the length of the longest chain ending with the word at that index. Initialize all elements to 1 because each word forms a chain of length 1 by default.
   * Initialize an integer variable `maxLen` to 1, which will be used to keep track of the maximum chain length found so far.
4. DP Loop:
   * Iterate through the `words` vector using a nested for loop. The outer loop iterates from `i = 1` to `n-1`, and the inner loop iterates from `j = 0` to `i-1`.
   * Inside the inner loop, check if `words[j]` is a subsequence of `words[i]` and if the length of `words[j]` plus 1 is equal to the length of `words[i]`. This checks if `words[i]` can be part of a longer chain.
   * If the conditions are met, update the `dp[i]` value to be the maximum of its current value and `dp[j] + 1`. This means that we consider extending the chain from word `j` to word `i`.
   * Update the `maxLen` variable with the maximum of its current value and `dp[i]`.
5. Return Result:
   * After the DP loop, return the value stored in `maxLen`, which represents the length of the longest string chain that can be formed using the input words.

## Time and Auxiliary Space Complexity

* Time Complexity: `O(n*n)`
* Auxiliary Space Complexity: `O(n)`

## Code (C++)

```cpp

class Solution {
public:
    static bool cmp(string a, string b){
        return a.length()<b.length();
    }
    bool isSubsequence(string s, string t) {
        int j=0;
        for(int i=0; i<t.length();i++){
            if(t[i]==s[j]){
                j++;
            }
        }
        if(s.length()==j)return true;
        return false;
    }

    int longestStrChain(vector<string>& words) {
        sort(words.begin(),words.end(),cmp);
        int n=words.size();
        vector<int> dp(n, 1);
        int maxLen = 1;
        
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(isSubsequence(words[j], words[i]) && words[j].length()+1==words[i].length()){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

```

## Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our [discussion section](https://leetcode.com/discuss/general-discussion). We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a `⭐ star` to the [rishabhv12/Daily-Leetcode-Solution](https://github.com/rishabhv12/Daily-Leetcode-Solution) repository.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code-render.gitbook.io/leetcode-editorials/09-september/23-longest-string-chain.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.