<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(int i, string s, int k, int prev,  vector<vector<int>>&mem){
//     if(i>=s.length()){
//         return mem[i][prev+1]=0;
//     }
//     if(mem[i][prev+1] != -1){
//         return mem[i][prev+1];
//     }
//     int ans = -1e8;
//     if(prev ==-1 || abs(s[i]-s[prev])<=k){
//         ans = max(ans,1+ solve(i+1, s, k, i, mem));
//     }
//     int a = solve(i+1, s, k, prev, mem);
//     return mem[i][prev+1]= max(ans, a);
// }
int solve2(string s, int k){
    int n = s.length();
        //vector<vector<int>>dp(n+1, vector<int>(n+1, 0));
        vector<int>prev(27, 0);
        // for(int i=0; i<=n; i++){
        //     dp[n][i]=0;
        // }
        for(int i=n-1; i>=0; i--){
            vector<int>curr(27, 0);
            for(int j=0; j<27; j++){
                int ans = INT_MIN;
                if(j-1==-1 || abs(s[i]-('a'+j-1))<=k){
                    ans = max(ans, 1+prev[(s[i]-'a') +1 ]);
                }
                ans = max(ans, prev[j]);
                curr[j]= ans;
            }
            prev = curr;
        }
        return prev[0];
}
    int longestIdealString(string s, int k) {
        int n = s.length();
       // vector<vector<int>>mem(n+1, vector<int>(n+1, -1));
        //return solve(0, s, k, -1, mem);
        return solve2(s, k);
    }
};
101386