Problem of The Day: Longest Ideal Subsequence

Problem Statement

Memoization approach - Memory Limit Exceeded

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        res = float('-inf')
        @cache
        def dfs(i, curr, length):
            if i >= len(s):
                return length

            take = skip = 0
            if abs(ord(s[i]) - ord(curr)) <= k:
                take = dfs(i + 1, s[i], length + 1)
            skip = dfs(i + 1, curr, length)
            return max(take, skip)

        for i in range(len(s)):
            res = max(res, dfs(i + 1, s[i], 1))

        return res if res != float('-inf') else 1

Editorial Solution

Top down - memoization approach

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        N = len(s)

        # Initialize all dp values to -1 to indicate non-visited states
        dp = [[-1] * 26 for _ in range(N)]

        def dfs(i: int, c: int, dp: list, s: str, k: int) -> int:
            # Memoized value
            if dp[i][c] != -1:
                return dp[i][c]

            # State is not visited yet
            dp[i][c] = 0
            match = c == (ord(s[i]) - ord('a'))
            if match:
                dp[i][c] = 1

            # Non base case handling
            if i > 0:
                dp[i][c] = dfs(i - 1, c, dp, s, k)
                if match:
                    for p in range(26):
                        if abs(c - p) <= k:
                            dp[i][c] = max(dp[i][c], dfs(i - 1, p, dp, s, k) + 1)
            return dp[i][c]

        # Find the maximum dp[N-1][c] and return the result
        res = 0
        for c in range(26):
            res = max(res, dfs(N - 1, c, dp, s, k))
        return res

Bottom up - dynamic programming

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        N = len(s)
        dp = [0] * 26

        res = 0
        # Updating dp with the i-th character
        for i in range(N):
            curr = ord(s[i]) - ord('a')
            best = 0
            for prev in range(26):
                if abs(prev - curr) <= k:
                    best = max(best, dp[prev])

            # Append s[i] to the previous longest ideal subsequence
            dp[curr] = max(dp[curr], best + 1)
            res = max(res, dp[curr])
        return res