<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:
    //    int solve(string s, int k , int index,char prev,vector<vector<int>> &dp ){
    //     if(index == s.size()) return 0;
    //     int take = INT_MIN;
    // if(dp[index][prev-'a']!=-1) return dp[index][prev-'a'];

    //    if(prev == 'z' +1 || abs(s[index] - prev) <=k ) { take = 1 + solve(s, k, index+1, s[index],dp);}

    // int  n_take = solve(s, k , index+1, prev,dp);
 
        
    //     return dp[index][prev-'a'] = max(take,n_take);
    // }
int tab(string s, int k ){
     vector<vector<int>> dp(s.size()+2,vector<int>(28,0));
     int prev = 26;
     for(int index = s.size()-1 ; index>= 0;index--){
        int x = s[index] - 'a';
        for(int prev = 26; prev>=0 ; prev--){
        int take = INT_MIN;
    
       if(prev == 26 || abs(s[index] -'a' - prev) <=k ) { take = 1 + dp[index+1][s[index]-'a'];}

         int  n_take = dp[index+ 1][prev];
 
        
        dp[index][prev] = max(take,n_take);
        }
     }
     return dp[0][26];
}
    int longestIdealString(string s, int k){
        // vector<vector<int>> dp(s.size()+1,vector<int>(27,-1));
        // return solve(s,k,0,'z'+1,dp);
        return tab(s,k);
    }
};
150048