<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 longestIdealString(string s, int k) {
        int n = s.length();
        vector<vector<int>> dp(n + 1, vector<int>(27, 0));

        for (int idx = 1; idx <= n; ++idx) {
            int curCharIndex = s[idx - 1] - 'a';

            for (char prev = 'a'; prev <= 'z'; ++prev) {
                int prevIdx = prev - 'a';

                // Option 1: Do not take the current character
                dp[idx][prevIdx] = max(dp[idx][prevIdx], dp[idx - 1][prevIdx]);

                // Option 2: Take the current character if the condition is met
                if (abs(curCharIndex - prevIdx) <= k) {
                    dp[idx][curCharIndex] = max(dp[idx][curCharIndex], 1 + dp[idx - 1][prevIdx]);
                }
            }

            // Handle the case where no previous character is taken
            dp[idx][curCharIndex] = max(dp[idx][curCharIndex], 1 + dp[idx - 1][26]);

            // Update the state where no character is taken before this character
            dp[idx][26] = max(dp[idx][26], dp[idx - 1][26]);
        }

        // Find the maximum value in the last row of the dp array
        int maxLength = 0;
        for (int j = 0; j < 27; ++j) {
            maxLength = max(maxLength, dp[n][j]);
        }

        return maxLength;
    }
};

114658