Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

※ 引述 《enmeitiryous (enmeitiryous)》 之銘言：
: 　
: 1653 minimun deletion make string balance
: 題目:
: 給你一個只有a,b兩種字母構成的字串s，求最少的deletion數使的新字串中
: a一定出現在任一b前面
: 　


思路:
建立一個陣列
記錄當前位子出現的a b
利用前綴合來知道如果在這個位子的話
要刪除多少a 或b可以讓字串符合條件

或是
我直接全部刪掉一種
姆咪


```cpp
class Solution {
public:
    int minimumDeletions(string s)
    {
        int len = s.size();
        int as= 0;
        int bs=0;
        vector<int> aaa(len , 0);
        vector<int> bbb(len , 0);

        int res = len;

        for(int i = 0; i < len ; i++)
        {
            if(s[i] == 'a')as++;
            aaa[i] = as;
            if(s[i] == 'b')bs++;
            bbb[i] = bs;
        }

        if(as == 0)return 0;
        if(bs == 0)return 0;

        for(int i = 0 ; i < len ; i ++)
        {
            res = min(bbb[i] + aaa[len-1] - aaa[i] , res);
        }

        res = min(aaa[len-1] , res);
        res = min(bbb[len-1] , res);

        return res;

    }
};
```



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.5.215 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722309240.A.464.html
推 DJYOMIYAHINA: 我好崇拜你
→ SydLrio: 你有什麼用
推 JIWP: 我好崇拜你