MediumNo. 2370
Longest Ideal Subsequence — LeetCode 2370 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Hash Table, String, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
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
- Time
- O(n)
- Space · auxiliary
- O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
| 0691 | Stickers to Spell Word | Hard |
| 0792 | Number of Matching Subsequences | Medium |
| 0828 | Count Unique Characters of All Substrings of a Given String | Hard |
| 1048 | Longest String Chain | Medium |
Frequently asked questions
- How hard is LeetCode 2370. Longest Ideal Subsequence?
LeetCode 2370. Longest Ideal Subsequence is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2370. Longest Ideal Subsequence?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2370. Longest Ideal Subsequence?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2370. Longest Ideal Subsequence cover?
LeetCode 2370. Longest Ideal Subsequence is tagged Hash Table, String and Dynamic Programming on LeetCode.