<p>You are given a string <code>s</code> consisting of lowercase letters and an integer <code>k</code>. We call a string <code>t</code> <strong>ideal</strong> if the following conditions are satisfied:</p>

<ul>
	<li><code>t</code> is a <strong>subsequence</strong> of the string <code>s</code>.</li>
	<li>The absolute difference in the alphabet order of every two <strong>adjacent</strong> letters in <code>t</code> is less than or equal to <code>k</code>.</li>
</ul>

<p>Return <em>the length of the <strong>longest</strong> ideal string</em>.</p>

<p>A <strong>subsequence</strong> is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.</p>

<p><strong>Note</strong> that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of <code>&#39;a&#39;</code> and <code>&#39;z&#39;</code> is <code>25</code>, not <code>1</code>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;acfgbd&quot;, k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest ideal string is &quot;acbd&quot;. The length of this string is 4, so 4 is returned.
Note that &quot;acfgbd&quot; is not ideal because &#39;c&#39; and &#39;f&#39; have a difference of 3 in alphabet order.</pre>

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

<pre>
<strong>Input:</strong> s = &quot;abcd&quot;, k = 3
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest ideal string is &quot;abcd&quot;. The length of this string is 4, so 4 is returned.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= k &lt;= 25</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

// class Solution{
// public:
//     vector<vector<int>>dp;
//     int helper(string& s,int ind,int k,int last){
//         if(ind>=s.length())return 0;
//         int l=0,r=0;
//         if(last!=-1 && dp[ind][last]!=-1)return dp[ind][last];
//         l=helper(s,ind+1,k,last);
//         if(last==-1 || abs(last-(s[ind]-'a'))<=k){
//             r=1+helper(s,ind+1,k,s[ind]-'a');
//         }
//         if(last!=-1)dp[ind][last]=max(l,r);
//         return max(l,r);
//     }
//     int longestIdealString(string& s, int k) {
//         dp.resize(s.length()+1,vector<int>(26,-1));
//         return helper(s,0,k,-1);
//     }
// };
class Solution {
public:
    int dp[100001][26]; // Assuming the maximum length of string s is 1000

    int helper(string& s, int ind, int k, int last) {
        if (ind >= s.length()) return 0;
        int l = 0, r = 0;
        if (last != -1 && dp[ind][last] != -1) return dp[ind][last];
        
        l = helper(s, ind + 1, k, last);
        
        if (last == -1 || abs(last - (s[ind] - 'a')) <= k) {
            r = 1 + helper(s, ind + 1, k, s[ind] - 'a');
        }
        
        if (last != -1) dp[ind][last] = max(l, r);
        
        return max(l, r);
    }

    int longestIdealString(string& s, int k) {
        memset(dp, -1, sizeof(dp)); // Initialize the dp array with -1
        return helper(s, 0, k, -1);
    }
};

class Solution2 {
public:
    int longestIdealString(string& s, int k) {
        vector<int> dp(26, 0); // dp array to store the max length of ideal string ending with each character
        for (char c : s) {
            int idx = c - 'a';
            int max_len = 0;
            // Check the range of indices that differ by at most k
            for (int i = max(0, idx - k); i <= min(25, idx + k); ++i) {
                max_len = max(max_len, dp[i]);
            }
            dp[idx] = max_len + 1;
        }
        return *max_element(dp.begin(), dp.end());
    }
};

26183