23.08.13 Today’s Leetcode

2370. Longest Ideal Subsequence (medium)

TLE at 35/90

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        def get_diff(a, b):
            return abs(ord(a) - ord(b))

        n = len(s)
        res = -1

        @functools.lru_cache(None)
        def dfs(i, cur):
            nonlocal res
            if i >= n:
                res = max(res, len(cur))
                return
            if cur:
                if get_diff(cur[-1], s[i]) <= k:
                    dfs(i + 1, cur + s[i])
                dfs(i + 1, cur)
            else:
                dfs(i + 1, cur + s[i])
                dfs(i + 1, cur)
    
        dfs(0, '')

        return res

Amazing DP with memoization

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        dp = [0] * 26
        for ch in s:
            i = ord(ch) - ord("a")
            dp[i] = 1 + max(dp[max(0, i - k) : min(26, i + k + 1)])
        return max(dp)