文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個字符串 s ，它僅包含字符 'a' 和 'b'???? 。

你可以刪除 s 中任意數目的字符，使得 s 平衡 。
我們稱 s 平衡的 當不存在下標對 (i,j) 滿足 i < j 且 s[i] = 'b' 同時 s[j]= 'a' 。

請你返回使 s 平衡 的 最少 刪除次數。

示例 1： 輸入：s = "aababbab" 輸出：2 解釋：你可以選擇以下任意一種方案： 下標從 0 開始，刪除第 2 和第 6 個字符（"aababbab" -> "aaabbb"）， 下標從 0 開始，刪除第 3 和第 6 個字符（"aababbab" -> "aabbbb"）。示例 2： 輸入：s = "bbaaaaabb" 輸出：2 解釋：唯一的最優解是刪除最前面兩個字符。提示： 1 <= s.length <= 10^5 s[i] 要么是 'a' 要么是 'b'? 。?

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-deletions-to-make-string-balanced
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• dpa, dpb 表示以 a， b 結尾的情況下，最少的刪除次數

class Solution { public:int minimumDeletions(string s) {int n = s.size();vector<int> dpa(n, 0), dpb(n, 0);if(s[0] == 'a')dpb[0] = 1;//以 b 結尾需要刪除1次elsedpa[0] = 1;for(int i = 1; i < n; ++i){if(s[i] == 'a'){dpa[i] = dpa[i-1];dpb[i] = min(dpa[i-1]+1, dpb[i-1]+1);}else{dpa[i] = dpa[i-1]+1;dpb[i] = min(dpa[i-1], dpb[i-1]);}}return min(dpa[n-1], dpb[n-1]);} };

172 ms 50.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1653. 使字符串平衡的最少删除次数（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。