Re: [閒聊] 每日leetcode

[JerryChungYC (JerryChung)]

https://leetcode.com/problems/minimum-deletions-to-make-string-balanced

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

思路：我也不知道
沒 先上程式碼

Python Code:

class Solution:
    def minimumDeletions(self, s: str) -> int:
        slen = result = len(s)
        sa = s.count('a')
        b = 0
        for i in range(slen+1):
            result = min(result, 2*b - i + sa)
            if i != slen and s[i] == 'b':
                b += 1
        return result

b 原本是 s[:i].count('b') 但發現每次循環都 count 的話會 TLE
2*b - i + sa = b - i + sa + b = b + (sa - (i - b))
全部的a - 前i個當中a的數量 = 位置i到結尾的a的數量
反正就是整合在一起(( 一開始的想法是 s[:i].count('b') + s[i:].count('a')

再補一下
b = s[:i].count('b')  # 前i個當中b的數量
s[i:].count('a')
= s.count('a') - (i - b)  # a變成只要計算一次就好 所以丟出迴圈

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.52.67 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722315726.A.05F.html
推 Smallsh: 大師
推 oin1104: 大師
推 JenniferLope: 大師
※ 編輯: JerryChungYC (60.251.52.67 臺灣), 07/30/2024 13:08:32
推 dont: 大師
推 sustainer123: 大師
※ 編輯: JerryChungYC (60.251.52.67 臺灣), 07/30/2024 13:20:19