1653.使字符串平衡的最少删除次数

链接：1653.使字符串平衡的最少删除次数
难度：Medium
标签：栈、字符串、动态规划
简介：请你返回使 s 平衡 的 最少 删除次数。

题解 1 - rust

• 编辑时间：2023-03-06
• 执行用时：16ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
        pub fn minimum_deletions(s: String) -> i32 {
            let (mut dp, mut b) = (0, 0);
            for c in s.chars() {
                if c == 'a' {
                    dp = b.min(dp + 1);
                } else {
                    b += 1;
                }
            }
            dp
        }
    }

题解 2 - cpp

• 编辑时间：2023-03-06
• 执行用时：64ms
• 内存消耗：21.6MB
• 编程语言：cpp
• 解法介绍：遍历到b的时候不做处理，遍历到a的时候考虑删除当前a或者删除前面的b。

class Solution {
public:
    int minimumDeletions(string s) {
        int dp = 0, b = 0;
        for (auto &c : s) {
            if (c == 'a') dp = min(dp + 1, b);
            else b += 1;
        }
        return dp;
    }
};

题解 3 - python

• 编辑时间：2023-03-06
• 执行用时：300ms
• 内存消耗：15.5MB
• 编程语言：python
• 解法介绍：同上。

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