Можно ли решить LeetCode 1653 с помощью рекурсии?

Я пытаюсь решить проблему LeetCode 1653. Минимальное количество удалений для балансировки строк:

Вам дана строка s, состоящая только из символов 'a' и 'b'​​​​.

Вы можете удалить любое количество символов в s, чтобы сделать s сбалансированным. s сбалансирован, если не существует пары индексов (i,j) такой, что i < j и s[i] = 'b' и s[j]= 'a'.

Верните минимальное количество удалений, необходимое для балансировки s.

Ограничения:

• 1 <= s.length <= 105
• s[i] — это 'a' или 'b'​​.

Пример 1:

Ввод: s = "aababbab"
Вывод: 2
Пояснение: Вы можете:
Удалите символы в позициях 2 и 6 с нулевым индексом («aababbab» -> «aaabbb»), или
Удалите символы в позициях 3 и 6 с нулевым индексом («aababbab» -> «aabbbb»)

Я понимаю, что оптимальным решением является использование DP или какого-либо итерационного подхода, но мне интересно, возможно ли это конкретно с помощью рекурсии.

Я изначально сделал так:

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)

Кажется, он проходит тестовые случаи, когда я пытаюсь запустить его на 300 мс, но когда я пытаюсь отправить решение, я получаю ошибку превышения лимита памяти. Как это можно решить с помощью рекурсии в пределах срока?