能否用递归解决LeetCode 1653：使字符串平衡的最少删除次数问题？

问题描述 #

给定仅由字符'a'和'b'组成的字符串s。你可以删除s中的任意数量字符，使s达到平衡状态。当不存在索引对(i,j)满足i < j且s[i] = 'b'、s[j] = 'a'时，s是平衡的。返回使s达到平衡所需的最少删除次数。

约束条件：

• 1 <= s.length <= 10^5
• s[i] 为'a'或'b'

示例1：
输入：s = "aababbab"
输出：2
解释：你可以选择：
删除索引2和6处的字符（"aababbab" -> "aaabbb"），或者
删除索引3和6处的字符（"aababbab" -> "aabbbb"）

我的递归尝试 #

我知道最优解法是动态规划或迭代方法，但想确认是否可以用递归实现。我最初的实现如下：

class Solution:    
    def minimumDeletions(self, s: str) -> int:        
        @lru_cache(None)        
        def dfs(index, last_char):            
            if index == len(s):                
                return 0            
            if s[index] >= last_char:                
                keep = dfs(index + 1, s[index])                
                delete = 1 + dfs(index + 1, last_char)                
                return min(keep, delete)            
            else:                
                return 1 + dfs(index + 1, last_char)        
        return dfs(0, 'a')

但该实现未剪枝已超过当前最小删除次数的路径。于是我尝试了第二种实现：

class Solution:    
    def minimumDeletions(self, s: str) -> int:        
        self.min_deletions = float('inf')         
        memo = {}        
        def dfs(index, last_char, current_deletions):            
            if current_deletions >= self.min_deletions:                
                return float('inf')            
            if index == len(s):                
                self.min_deletions = min(self.min_deletions, current_deletions)                
                return 0            
            if (index, last_char) in memo:                
                return memo[(index, last_char)]            
            if s[index] >= last_char:                
                keep = dfs(index + 1, s[index], current_deletions)                
                delete = 1 + dfs(index + 1, last_char, current_deletions + 1)                
                result = min(keep, delete)            
            else:                
                result = 1 + dfs(index + 1, last_char, current_deletions + 1)            
            memo[(index, last_char)] = result            
            return result        
        return dfs(0, 'a', 0)

该实现本地测试耗时300ms左右能通过用例，但提交时出现内存超限错误。请问如何在时间限制内用递归解决该问题？

递归优化方案 #

由于题目字符串长度可达1e5，普通递归会直接触发栈溢出（Python默认递归深度仅约1000），同时无节制的记忆化会导致内存占用过高。以下是可行的递归优化思路：

1. 分治递归（避免栈溢出） #

把字符串分成左右两部分递归处理，递归深度降至O(logn)（对于1e5长度的字符串，仅约17层），完全规避栈溢出问题，同时减少重叠子问题的数量：

class Solution:
    def minimumDeletions(self, s: str) -> int:
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dfs(l, r, left_last, right_first):
            if l > r:
                return 0
            if l == r:
                return 0 if left_last <= s[l] else 1
            
            mid = (l + r) // 2
            # 计算左半部分以'a'/'b'结尾的最小删除次数
            left_a = dfs(l, mid, left_last, 'a')
            left_b = dfs(l, mid, left_last, 'b')
            # 计算右半部分以'a'/'b'开头的最小删除次数
            right_a = dfs(mid+1, r, 'a', right_first)
            right_b = dfs(mid+1, r, 'b', right_first)
            
            # 合并结果：左半末尾为a时，右半开头可以是a或b；左半末尾为b时，右半开头只能是b
            option1 = left_a + min(right_a, right_b)
            option2 = left_b + right_b
            return min(option1, option2)
        
        return dfs(0, len(s)-1, 'a', 'b')

2. 优化记忆化存储 #

原实现用字典存储(index, last_char)状态，可简化为两个变量记录当前索引下，以上一个字符为'a'或'b'时的最小删除次数，将内存复杂度从O(n)降至O(1)。不过结合递归深度问题，分治方案仍是更优选择。

3. 手动模拟栈（迭代式递归） #

如果不想用分治，可手动用栈数据结构模拟递归过程，完全避免递归栈溢出：

class Solution:
    def minimumDeletions(self, s: str) -> int:
        stack = [(0, 'a', 0)]
        min_deletions = float('inf')
        
        while stack:
            index, last_char, current_deletions = stack.pop()
            
            if current_deletions >= min_deletions:
                continue
            if index == len(s):
                min_deletions = min(min_deletions, current_deletions)
                continue
            
            # 先压入删除当前字符的分支（栈是后进先出，保证先处理保留分支）
            stack.append((index + 1, last_char, current_deletions + 1))
            # 再压入保留当前字符的分支（仅当符合条件时）
            if s[index] >= last_char:
                stack.append((index + 1, s[index], current_deletions))
        
        return min_deletions

补充说明 #

如果追求极致性能，最优解仍是O(n)时间、O(1)空间的迭代动态规划：

class Solution:
    def minimumDeletions(self, s: str) -> int:
        delete_a = 0
        delete_b = 0
        for c in s:
            if c == 'a':
                delete_b += 1
            else:
                delete_a = min(delete_a + 1, delete_b)
        return min(delete_a, delete_b)

但上述递归优化方案已能满足题目要求，在时间和内存限制内通过测试。

内容的提问来源于stack exchange，提问作者Vanillaice