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^5
  • 0 <= k <= 25
  • s 由小写英文字母组成

解题思路

这是一个经典的动态规划问题。我们需要找到满足相邻字符差值不超过 k 的最长子序列。

思路分析：

  1. 状态定义：我们可以用 dp[c] 表示以字符 c 结尾的最长理想子序列长度。

  2. 状态转移：当我们遍历到字符 s[i] 时，我们需要考虑所有可能的前一个字符。如果前一个字符与当前字符的差值不超过 k，那么我们就可以将当前字符加入到以前一个字符结尾的序列中。

  3. 转移方程：对于当前字符 c，我们需要在所有满足 |prev - c| <= k 的字符 prev 中找到最长的序列长度，然后加 1。

  4. 优化：由于只有 26 个小写字母，我们可以直接用数组存储每个字母结尾的最长序列长度。

算法步骤：

  • 初始化一个长度为 26 的数组 dp，表示以每个字母结尾的最长理想子序列长度
  • 遍历字符串 s 的每个字符
  • 对于当前字符，在所有满足条件的前驱字符中找最大值
  • 更新当前字符对应的 dp 值
  • 返回 dp 数组中的最大值

时间复杂度为 O(n × 26)，空间复杂度为 O(26)，其中 n 是字符串长度。

代码实现

class Solution {
public:
    int longestIdealString(string s, int k) {
        vector<int> dp(26, 0);
        
        for (char c : s) {
            int idx = c - 'a';
            int maxLen = 0;
            
            // 检查所有可能的前驱字符
            for (int prev = 0; prev < 26; prev++) {
                if (abs(prev - idx) <= k) {
                    maxLen = max(maxLen, dp[prev]);
                }
            }
            
            dp[idx] = maxLen + 1;
        }
        
        return *max_element(dp.begin(), dp.end());
    }
};

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        dp = [0] * 26
        
        for c in s:
            idx = ord(c) - ord('a')
            max_len = 0
            
            # 检查所有可能的前驱字符
            for prev in range(26):
                if abs(prev - idx) <= k:
                    max_len = max(max_len, dp[prev])
            
            dp[idx] = max_len + 1
        
        return max(dp)

public class Solution {
    public int LongestIdealString(string s, int k) {
        int[] dp = new int[26];
        
        foreach (char c in s) {
            int idx = c - 'a';
            int maxLen = 0;
            
            // 检查所有可能的前驱字符
            for (int prev = 0; prev < 26; prev++) {
                if (Math.Abs(prev - idx) <= k) {
                    maxLen = Math.Max(maxLen, dp[prev]);
                }
            }
            
            dp[idx] = maxLen + 1;
        }
        
        return dp.Max();
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestIdealString = function(s, k) {
    const dp = new Array(26).fill(0);
    
    for (const c of s) {
        const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
        let maxLen = 0;
        
        // 检查所有可能的前驱字符
        for (let prev = 0; prev < 26; prev++) {
            if (Math.abs(prev - idx) <= k) {
                maxLen = Math.max(maxLen, dp[prev]);
            }
        }
        
        dp[idx] = maxLen + 1;
    }
    
    return Math.max(...dp);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n × 26) = O(n)，其中 n 是字符串长度，对于每个字符需要检查 26 个可能的前驱字符
空间复杂度O(26) = O(1)，只需要常数大小的数组存储每个字母结尾的最长序列长度

相关题目