What is the main pattern used to solve the Longest Ideal Subsequence problem?

The main pattern is state transition dynamic programming, where the solution relies on transitioning through states efficiently, often using a hash map.

How does dynamic programming apply to the Longest Ideal Subsequence problem?

Dynamic programming helps by storing the lengths of the longest subsequences ending at each character in the string, allowing for optimal transitions based on the alphabetic difference condition.

What is the time complexity of the Longest Ideal Subsequence problem?

The time complexity is O(N * L), where N is the length of the string and L is the number of distinct characters (26 for lowercase English letters).

Can we solve the Longest Ideal Subsequence problem without using dynamic programming?

While it's possible, using dynamic programming is the most efficient approach. A brute-force solution would have a time complexity of O(N^2), which is not scalable for large inputs.

How does using a hash map improve the solution for this problem?

Using a hash map allows for faster lookup and update of the longest subsequences ending with specific characters, reducing the need for nested loops and improving time complexity.

#2370

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长理想子序列

给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是理想字符串： t 是字符串 s 的一个子序列。 t 中每两个相邻字母在字母表中位次的绝对差值小于或等于 k 。返回最长理想字符串的长度。字符串的子序列同样是一个字符串，并且子序列还满足…

哈希表字符串动态规划

题目描述

给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ：

t 是字符串 s 的一个子序列。
t 中每两个相邻字母在字母表中位次的绝对差值小于或等于 k 。

返回最长理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。

注意：字母表顺序不会循环。例如，'a' 和 'z' 在字母表中位次的绝对差值是 25 ，而不是 1 。

示例 1：

输入：s = "acfgbd", k = 2
输出：4
解释：最长理想字符串是 "acbd" 。该字符串长度为 4 ，所以返回 4 。
注意 "acfgbd" 不是理想字符串，因为 'c' 和 'f' 的字母表位次差值为 3 。

示例 2：

输入：s = "abcd", k = 3
输出：4
解释：最长理想字符串是 "abcd" ，该字符串长度为 4 ，所以返回 4 。

提示：

1 <= s.length <= 10⁵
0 <= k <= 25
s 由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

设 $dp[i]$ 表示以字符 $s[i]$ 结尾的最长理想子序列的长度，利用哈希表 $d$ 记录每个字符最新出现的位置。初始时 $dp[0]=1$ , $d[s[0]]=0$ 。

在 $[1,..n-1]$ 范围内的每个字符 $s[i]$ ，获取它所有前一个合法字符的位置 $j$ ，那么 $dp[i]=max(dp[i], dp[j]+1)$ 。

答案为 $dp$ 中的最大值。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

speed

复杂度分析

指标	值
时间	O(NL)
空间	O(L)

psychology

面试官常问的追问

外企场景

question_mark
The candidate correctly applies dynamic programming to solve the problem by defining an optimal state transition.
question_mark
The candidate uses a hash map efficiently to store and retrieve subsequence lengths, reducing time complexity.
question_mark
The candidate demonstrates a clear understanding of subsequence problems, especially the constraints defined by the alphabetic difference k.

warning

常见陷阱

外企场景

error
Failing to optimize the solution by using a hash map can lead to O(N^2) time complexity, which is inefficient for large strings.
error
Not correctly tracking the transitions between subsequences may result in incorrect or suboptimal solutions.
error
The candidate might not consider edge cases such as the minimum or maximum values of k, or strings with a single character.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variants where the string contains uppercase letters, expanding the alphabetic range.
arrow_right_alt
Modify the problem to allow only a fixed number of deletions, adding a layer of complexity.
arrow_right_alt
Test the solution with varying k values to examine how it handles different constraints in the problem.

help

常见问题

外企场景

继续练习

#2266 统计打字方案数 #2262 字符串的总引力 #2606 找到最大开销的子字符串