Hard

题目描述

给你一个由小写英文字母组成的字符串 s。

你可以执行以下操作任意次数（包括零次）：

  • 移除字符串中任意一对相邻且在字母表中连续的字符，顺序不限（例如，‘a’ 和 ‘b’，或 ‘b’ 和 ‘a’）。
  • 将剩余字符向左移动以填补空隙。

返回执行最优操作后能得到的字典序最小的字符串。

注意：字母表是循环的，因此 ‘a’ 和 ‘z’ 是连续的。

示例 1：

输入：s = "abc"
输出："a"
解释：
从字符串中移除 "bc"，剩下 "a"。
无法进行进一步操作。因此，所有可能移除后的字典序最小字符串是 "a"。

示例 2：

输入：s = "bcda"
输出：""
解释：
从字符串中移除 "cd"，剩下 "ba"。
从字符串中移除 "ba"，剩下 ""。
无法进行进一步操作。因此，所有可能移除后的字典序最小字符串是 ""。

示例 3：

输入：s = "zdce"
输出："zdce"
解释：
从字符串中移除 "dc"，剩下 "ze"。
对 "ze" 无法进行进一步操作。
然而，由于 "zdce" 的字典序小于 "ze"，所有可能移除后的最小字符串是 "zdce"。

约束条件：

  • 1 <= s.length <= 250
  • s 仅由小写英文字母组成。

解题思路

这是一个动态规划问题，需要分两个步骤解决：

第一步：确定可移除的区间 使用动态规划计算哪些子串可以被完全移除。定义 canRemove[i][j] 表示子串 s[i...j] 是否可以被完全移除。

  • 长度为2的子串：如果两个字符在字母表中相邻（考虑循环），则可移除
  • 长度大于2的子串：如果存在分割点 k，使得左右两部分都可移除，则整个子串可移除

第二步：构造字典序最小结果 定义 dp[i] 为从位置 i 到字符串末尾能构造的字典序最小字符串。

对于每个位置 i，有两种选择：

  1. 保留字符 s[i]，结果为 s[i] + dp[i+1]
  2. 如果存在位置 j > i 使得区间 [i+1, j-1] 可以完全移除，则可以跳过这个区间，选择字符 s[j]，结果为 s[j] + dp[j+1]

在所有可能的选择中取字典序最小的结果。

这种方法确保我们能找到全局最优解，因为动态规划会考虑所有可能的移除组合。

代码实现

class Solution {
public:
    string lexicographicallySmallestString(string s) {
        int n = s.length();
        
        // Step 1: Calculate which substrings can be completely removed
        vector<vector<bool>> canRemove(n, vector<bool>(n, false));
        
        // Check pairs of adjacent characters
        for (int i = 0; i < n - 1; i++) {
            if (isAdjacent(s[i], s[i + 1])) {
                canRemove[i][i + 1] = true;
            }
        }
        
        // Check longer substrings
        for (int len = 4; len <= n; len += 2) { // Only even lengths can be completely removed
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int k = i + 1; k < j; k += 2) {
                    if (canRemove[i][k] && canRemove[k + 1][j]) {
                        canRemove[i][j] = true;
                        break;
                    }
                }
            }
        }
        
        // Step 2: Build the lexicographically smallest string
        vector<string> dp(n + 1);
        dp[n] = "";
        
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = s[i] + dp[i + 1]; // Option 1: keep s[i]
            
            // Option 2: skip some characters if possible
            for (int j = i + 1; j < n; j++) {
                if (canRemove[i + 1][j - 1]) {
                    string candidate = s[j] + dp[j + 1];
                    if (candidate < dp[i]) {
                        dp[i] = candidate;
                    }
                }
            }
        }
        
        return dp[0];
    }
    
private:
    bool isAdjacent(char a, char b) {
        return abs(a - b) == 1 || (a == 'a' && b == 'z') || (a == 'z' && b == 'a');
    }
};

class Solution:
    def lexicographicallySmallestString(self, s: str) -> str:
        n = len(s)
        
        # Step 1: Calculate which substrings can be completely removed
        can_remove = [[False] * n for _ in range(n)]
        
        # Check pairs of adjacent characters
        for i in range(n - 1):
            if self.is_adjacent(s[i], s[i + 1]):
                can_remove[i][i + 1] = True
        
        # Check longer substrings
        for length in range(4, n + 1, 2):  # Only even lengths can be completely removed
            for i in range(n - length + 1):
                j = i + length - 1
                for k in range(i + 1, j, 2):
                    if can_remove[i][k] and can_remove[k + 1][j]:
                        can_remove[i][j] = True
                        break
        
        # Step 2: Build the lexicographically smallest string
        dp = [""] * (n + 1)
        
        for i in range(n - 1, -1, -1):
            dp[i] = s[i] + dp[i + 1]  # Option 1: keep s[i]
            
            # Option 2: skip some characters if possible
            for j in range(i + 1, n):
                if can_remove[i + 1][j - 1]:
                    candidate = s[j] + dp[j + 1]
                    if candidate < dp[i]:
                        dp[i] = candidate
        
        return dp[0]
    
    def is_adjacent(self, a: str, b: str) -> bool:
        return abs(ord(a) - ord(b)) == 1 or (a == 'a' and b == 'z') or (a == 'z' and b == 'a')

public class Solution {
    public string LexicographicallySmallestString(string s) {
        int n = s.Length;
        
        // Step 1: Calculate which substrings can be completely removed
        bool[,] canRemove = new bool[n, n];
        
        // Check pairs of adjacent characters
        for (int i = 0; i < n - 1; i++) {
            if (IsAdjacent(s[i], s[i + 1])) {
                canRemove[i, i + 1] = true;
            }
        }
        
        // Check longer substrings
        for (int len = 4; len <= n; len += 2) { // Only even lengths can be completely removed
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                for (int k = i + 1; k < j; k += 2) {
                    if (canRemove[i, k] && canRemove[k + 1, j]) {
                        canRemove[i, j] = true;
                        break;
                    }
                }
            }
        }
        
        // Step 2: Build the lexicographically smallest string
        string[] dp = new string[n + 1];
        dp[n] = "";
        
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = s[i] + dp[i + 1]; // Option 1: keep s[i]
            
            // Option 2: skip some characters if possible
            for (int j = i + 1; j < n; j++) {
                if (canRemove[i + 1, j - 1]) {
                    string candidate = s[j] + dp[j + 1];
                    if (string.Compare(candidate, dp[i]) < 0) {
                        dp[i] = candidate;
                    }
                }
            }
        }
        
        return dp[0];
    }
    
    private bool IsAdjacent(char a, char b) {
        return Math.Abs(a - b) == 1 || (a == 'a' && b == 'z') || (a == 'z' && b == 'a');
    }
}

var lexicographicallySmallestString = function(s) {
    function canRemove(a, b) {
        return Math.abs(a.charCodeAt(0) - b.charCodeAt(0)) === 1 || 
               (a === 'a' && b === 'z') || (a === 'z' && b === 'a');
    }
    
    function getMinString(str) {
        let stack = [];
        for (let char of str) {
            while (stack.length > 0 && canRemove(stack[stack.length - 1], char)) {
                stack.pop();
            }
            stack.push(char);
        }
        return stack.join('');
    }
    
    let memo = new Set();
    let queue = [s];
    let minResult = s;
    
    while (queue.length > 0) {
        let current = queue.shift();
        
        if (memo.has(current)) continue;
        memo.add(current);
        
        if (current < minResult) {
            minResult = current;
        }
        
        let reduced = getMinString(current);
        if (!memo.has(reduced) && reduced !== current) {
            queue.push(reduced);
        }
        
        for (let i = 0; i < current.length - 1; i++) {
            if (canRemove(current[i], current[i + 1])) {
                let newStr = current.slice(0, i) + current.slice(i + 2);
                if (!memo.has(newStr)) {
                    queue.push(newStr);
                }
            }
        }
    }
    
    return minResult;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n³)
空间复杂度O(n²)

其中 n 是字符串的长度。时间复杂度主要来自于计算可移除区间的 O(n³) 和构造结果的 O(n²)，空间复杂度来自于存储 DP 表格。