<p>You are given an array of <code>words</code> where each word consists of lowercase English letters.</p>

<p><code>word<sub>A</sub></code> is a <strong>predecessor</strong> of <code>word<sub>B</sub></code> if and only if we can insert <strong>exactly one</strong> letter anywhere in <code>word<sub>A</sub></code> <strong>without changing the order of the other characters</strong> to make it equal to <code>word<sub>B</sub></code>.</p>

<ul>
	<li>For example, <code>&quot;abc&quot;</code> is a <strong>predecessor</strong> of <code>&quot;ab<u>a</u>c&quot;</code>, while <code>&quot;cba&quot;</code> is not a <strong>predecessor</strong> of <code>&quot;bcad&quot;</code>.</li>
</ul>

<p>A <strong>word chain</strong><em> </em>is a sequence of words <code>[word<sub>1</sub>, word<sub>2</sub>, ..., word<sub>k</sub>]</code> with <code>k &gt;= 1</code>, where <code>word<sub>1</sub></code> is a <strong>predecessor</strong> of <code>word<sub>2</sub></code>, <code>word<sub>2</sub></code> is a <strong>predecessor</strong> of <code>word<sub>3</sub></code>, and so on. A single word is trivially a <strong>word chain</strong> with <code>k == 1</code>.</p>

<p>Return <em>the <strong>length</strong> of the <strong>longest possible word chain</strong> with words chosen from the given list of </em><code>words</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;b&quot;,&quot;ba&quot;,&quot;bca&quot;,&quot;bda&quot;,&quot;bdca&quot;]
<strong>Output:</strong> 4
<strong>Explanation</strong>: One of the longest word chains is [&quot;a&quot;,&quot;<u>b</u>a&quot;,&quot;b<u>d</u>a&quot;,&quot;bd<u>c</u>a&quot;].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;xbc&quot;,&quot;pcxbcf&quot;,&quot;xb&quot;,&quot;cxbc&quot;,&quot;pcxbc&quot;]
<strong>Output:</strong> 5
<strong>Explanation:</strong> All the words can be put in a word chain [&quot;xb&quot;, &quot;xb<u>c</u>&quot;, &quot;<u>c</u>xbc&quot;, &quot;<u>p</u>cxbc&quot;, &quot;pcxbc<u>f</u>&quot;].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;abcd&quot;,&quot;dbqca&quot;]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The trivial word chain [&quot;abcd&quot;] is one of the longest word chains.
[&quot;abcd&quot;,&quot;dbqca&quot;] is not a valid word chain because the ordering of the letters is changed.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 16</code></li>
	<li><code>words[i]</code> only consists of lowercase English letters.</li>
</ul>

class Solution {
public:
    bool is_pred(const string &a, const string &b) {
        int m = a.size(), n = b.size();
        if(m >= n || n - m != 1) return false;

        int i = 0, j = 0;
        while(i < a.size() && j < b.size()) {
            if(a[i] == b[j]) {
                i++;
            }
            j++;
        }

        return i == m;
    }

    int recursion(vector<string>& words, int idx, int prev) {
        if(idx >= words.size()) return 0;

        int take = 0;
        if(prev == -1 || is_pred(words[prev], words[idx])) {
            take = 1 + recursion(words, idx + 1, idx);
        }

        int skip = recursion(words, idx + 1, prev);

        return max(take, skip);
    }

    int memoization(vector<string>& words, vector<vector<int>> &dp, int idx, int prev) {
        if(idx >= words.size()) return 0;

        if(prev != -1 && dp[prev][idx] != -1) return dp[prev][idx];

        int take = 0;
        if(prev == -1 || is_pred(words[prev], words[idx])) {
            take = 1 + memoization(words, dp, idx + 1, idx);
        }

        int skip = memoization(words, dp, idx + 1, prev);

        if(prev != -1) {
            dp[prev][idx] = max(take, skip);
        }

        return max(take, skip);
    }

    int longestStrChain(vector<string>& words) {
        // it is also variation of LIS.
        // we first sort the given words in increasing order of their lengths.
        // then we need to check if we are taking the current word then it should be predecessor of previous word, to check that we create a helper function in which we send the previous word and current word
        // previous word should have one less length than current and it should be subsequence of the current word.
        // to check the subsequence we can take pointers which points to the character of each word and if both points to same character then we can increase the pointers and we can check if smaller word pointer reached at end.

        auto comparator = [](const string &x, const string &y) {
            return x.size() < y.size();
        };
        sort(words.begin(), words.end(), comparator);



        // Appraoch 1: recursion
        // return recursion(words, 0, -1); 
        
        int n = words.size();
        vector<vector<int>> dp(1001, vector<int>(1001, -1));
        return memoization(words, dp, 0, -1);

        // int ans = INT_MIN;
        // for(int i = 0; i < n; i++) {
        //     ans = max(ans, dp[i]);
        // }

        // return ans;
    }
};
384405