<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:
    # what is the range of values len(s) can take on? [1, 100000]
    # what is the range of values k can take on? [0, 25]
    # what is the range of values s[i] can take on? only lowercase english letters
    # can s be a null reference? no
    # we are returning a maximized integer length!
    # is the answer unique? yes
    # is the answer >= 0? yes

    # idea 0
    # brute force
    # try all (n choose k) letters where k in [1, n]
    #  create subsequence
    #  check each adjacent letter
    # record maximum length

    # idea 1
    # memoized dynamic programming + dfs + backtracking
    # record latest letter chosen
    # on each letter of s, choose to keep or delete said letter
    # make sure that if we keep the letter, the absolute difference
    #    between kept letter and latest letter is <= k
    # example 1
    # f
    # g
    # return 4
    # pseudocode
    # n = len(s)
    # dp_cache = {}
    # ans = float("inf")
    # def dp(idx,latestChar,lengthSoFar):
    #    if (idx,latestChar) in dp_cache:
    #         return lengthSoFar+dp_cache[(idx,latestChar)]
    #    if idx == n:
    #       return lengthSoFar
    #    # keep letter if possible
    #    keep = float("inf")
    #    if latestChar != None and abs(ord(s[idx])-ord(latestChar))<=k:
    #        keep = dp(idx+1,s[idx],lengthSoFar+1)
    #    # delete char
    #    delete = dp(idx+1,latestChar,lengthSoFar)
    #    res = min(keep,delete)
    #    dp_cache[(idx,latestChar)] = res
    #    return res
    # dp(0,None)
    # return ans
    
    def longestIdealString(self, s: str, k: int) -> int:
        # implement idea 1 (dynamic programming + dfs + backtracking) <<< TLE
        # n = len(s)
        # dp_cache = [[-1 for _ in range(26)] for _ in range(n+1)]
        # ans = float("-inf")
        # def dp(idx,latestChar):
        #     if latestChar!=None and dp_cache[idx][ord(latestChar)-ord('a')]!=-1:
        #         return dp_cache[idx][ord(latestChar)-ord('a')]
        #     if idx == n:
        #         return 0
        #     # keep letter if possible
        #     keep = float("-inf")
        #     if latestChar == None or abs(ord(s[idx])-ord(latestChar))<=k:
        #         keep = 1+dp(idx+1,s[idx])
        #     # delete char
        #     delete = float("-inf")
        #     if keep < n-(idx+1):
        #         delete = dp(idx+1,latestChar)
        #     res = max(keep,delete)
        #     if latestChar!=None:
        #         dp_cache[idx][ord(latestChar)-ord('a')] = res
        #     return res
        # return dp(0,None)
        
        # LeetCode Editorial Approach 1 (Top Down Memoized DP)
        n = len(s)
        dp = [[-1]*26 for _ in range(n)]
        def dfs(idx,latestCharAscii):
            if dp[idx][latestCharAscii]!=-1:
                return dp[idx][latestCharAscii]
            # state not visited
            dp[idx][latestCharAscii]=0
            match = latestCharAscii == (ord(s[idx])-ord('a'))
            if match:
                dp[idx][latestCharAscii]=1
            if idx>0: # not first character
                dp[idx][latestCharAscii] = dfs(idx-1,latestCharAscii)
                if match:
                    for c in range(26):
                        if abs(latestCharAscii-c)<=k:
                            dp[idx][latestCharAscii] = (max(
                                dp[idx][latestCharAscii],
                                dfs(idx-1,c)+1
                            ))
            return dp[idx][latestCharAscii]
        res = float("-inf")
        for c in range(26):
            res = max(res,dfs(n-1,c))
        return res
72000