最长理想子序列

难度: Medium

给你一个由小写字母组成的字符串 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 由小写英文字母组成

Submission

运行时间: 289 ms

内存: 16.4 MB

class Solution:
#     def longestIdealString(self, s: str, k: int) -> int:
#         n = len(s) 
#         dp = [1] * n 
# # dp[i]:以S[i]为结尾的字符串的最大长度

#         last_index_map = defaultdict(int)
#         for i in range(n):
#             for j in range(26):
#                 letter = chr(ord('a') + j)
#                 # print(letter)
#                 if abs(ord(letter) - ord(s[i])) > k: continue 
#                 if letter in last_index_map:
#                     idx = last_index_map[letter]
#                     dp[i] = max(dp[i], dp[idx]+1)
#             last_index_map[s[i]] = i 
#         return max(dp)
            

    def longestIdealString(self, s: str, k: int) -> int:
        dp = [0] * 128

        for c in s:
            ord_c = ord(c)
            dp[ord_c] = max(dp[ord_c - k: ord_c + k + 1]) + 1
            
        return max(dp)

Explain

该题解采用动态规划的方式来求解最长理想子序列的长度。dp数组的每个元素dp[ord(c)]表示以字符c结尾的最长理想子序列的长度。遍历给定字符串s中的每个字符c，计算以该字符结尾的最长理想子序列长度，方法是查看在字符c的ASCII码基础上前后k范围内的所有字符所记录的最长子序列长度，找到最大值后加1即为以字符c结尾的最长理想子序列的长度。最后，返回dp数组中的最大值即可。

时间复杂度: O(n*k)

空间复杂度: O(1)

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        dp = [0] * 128  # 创建大小为128的dp数组，对应所有可能的ASCII字符

        for c in s:  # 遍历字符串s中的每个字符
            ord_c = ord(c)  # 获取字符的ASCII值
            # 更新dp[ord_c]为当前字符c的前后k个ASCII范围内dp的最大值加1
            dp[ord_c] = max(dp[ord_c - k: ord_c + k + 1]) + 1
        
        return max(dp)  # 返回dp数组中的最大值，即为最长理想子序列的长度

Explore

是的，dp数组选择长度为128是因为ASCII码标准定义了128个字符（从0到127），包括控制字符和可打印字符。通过将dp数组的大小设置为128，可以直接使用字符的ASCII值作为索引，方便对每个可能的字符进行操作和记录。这样的设计简化了代码实现，同时确保了对所有ASCII字符的覆盖，从而不受限于特定类型的字符，如只有小写字母或只有数字等。

在该问题中，理想子序列允许序列中的字符在ASCII码表中相差至多k。因此，对于每个字符c，我们查找在其ASCII值前后k的范围内（即ord(c)-k到ord(c)+k）的所有字符对应的最长子序列长度，取这些长度的最大值再加1，即可得到以字符c结尾的最长理想子序列的长度。这样做的主要逻辑是利用已知的子问题（较短的理想子序列的长度）来解决更大的问题（以当前字符结束的理想子序列的长度），这是动态规划方法的核心思想。

是的，该算法通过使用大小为128的dp数组，覆盖了所有ASCII字符，包括控制字符、数字、大写字母、小写字母等。这种做法的优点在于算法的通用性和适用性更广，不受具体字符类型的限制。然而，这也可能带来潜在的问题，比如包括非可打印字符可能会对实际应用造成困扰，因为在某些情况下，这些字符可能不被期望出现在理想子序列中。

在Python中，列表切片操作可以自动处理边界问题。即如果索引超出了列表的开始或结束，Python会返回从开始到结束的有效切片。例如，如果ord_c-k小于0，切片会从索引0开始；如果ord_c+k超过127，切片会在索引127结束。这种特性使得代码能够在不进行额外边界检查的情况下正常运行，简化了代码的实现。