※ 引述《DJYOMIYAHINA (通通打死)》之铭言：
: 思路:
: for loop 下去
: 每个index的cost都会是
: 删掉前面所有的'b'跟后面所有的'a'
: 所需要的次数
: 就取所有cost的最小值就可
: def minimumDeletions(self, s: str) -> int:`
: a_cnt = s.count('a')
: a_cnt_cur, b_cnt_cur = 0, 0
: ans = len(s)
: for i,c in enumerate(s):
: if c == 'a':
: a_cnt_cur += 1
: ans = min(ans, b_cnt_cur + (a_cnt - a_cnt_cur))
: else:
: ans = min(ans, b_cnt_cur + (a_cnt - a_cnt_cur))
: b_cnt_cur += 1
: return ans
思路:
整个s走一遍
遇到stack[-1]是b且后面是a
stack就pop()
然后result += 1
其他情况就把c放进stack
Python Code:
class Solution:
def minimumDeletions(self, s: str) -> int:
stack = []
result = 0
for c in s:
if c == "a":
if stack and stack[-1] == "b":
result += 1
stack.pop()
else:
stack.append(c)
return result