Longest Ideal Subsequence — LeetCode 2370 Python Solution

The problem

You are given a string s consisting of lowercase letters and an integer k. We call a string t ideal if the following conditions are satisfied: t is a subsequence of the string s.

Example

Input

s = "acfgbd", k = 2

Output

4

Explanation

The longest ideal string is "acbd". The length of this string is 4, so 4 is returned.

Python solution

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        n = len(s)
        ans = 1
        dp = [1] * n
        d = {s[0]: 0}
        for i in range(1, n):
            a = ord(s[i])
            for b in ascii_lowercase:
                if abs(a - ord(b)) > k:
                    continue
                if b in d:
                    dp[i] = max(dp[i], dp[d[b]] + 1)
            d[s[i]] = i
        return max(dp)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2370. Longest Ideal Subsequence is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems