<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,char prev_ch,int curr,vector<vector<int>>&dp){

        if(curr>=s.size()){

            return 0;
        }

        if(dp[prev_ch-'a'][curr]!=-1){

            return dp[prev_ch-'a'][curr];
        }
        int include=0;
        if(prev_ch=='{' || abs(prev_ch-s[curr])<=k){

            include=1+solve(s,k,s[curr],curr+1,dp);
        }
        int exclude=solve(s,k,prev_ch,curr+1,dp);

        dp[prev_ch-'a'][curr]=max(include,exclude);
        return dp[prev_ch-'a'][curr];
    }
    int solve2(string &s,int &k){

        vector<vector<int>>dp(s.size()+1,vector<int>(27,0));

        for(int curr=s.size()-1 ; curr>=0 ; curr--){

            for(char prev_ch='z' ; prev_ch>='a'-1 ; prev_ch--){

                int include=0;
                if(prev_ch=='a'-1 || abs(prev_ch-s[curr])<=k){

                    include=1+dp[curr+1][s[curr]-'a'+1];
                }
                int exclude=dp[curr+1][prev_ch-'a'+1];
                dp[curr][prev_ch-'a'+1]=max(include,exclude);
            }
        }

        return dp[0][0];
    }
    int solve3(string &s,int &k){

        vector<int>prev1(s.size()+2,0);
        vector<int>prev2(s.size()+2,0);

        for(int curr=s.size()-1 ; curr>=0 ; curr--){

            for(int prev=curr-1 ; prev>=-1 ; prev--){

                int include=0;
                if(prev==-1 || abs(s[prev]-s[curr])<=k){

                    include=1+prev1[curr+1];
                }
                int exclude=prev1[prev+1];

                prev2[prev+1]=max(include,exclude);
            }
            prev1=prev2;
        }

        return prev1[0];  
    }
    int longestIdealString(string s, int k) {
        
        // vector<vector<int>>dp(27,vector<int>(s.size(),-1));//bole to 27

        // return solve(s,k,'z'+1,0,dp);

        return solve2(s,k);
        // return solve3(s,k);
    }
};
119081