Leetcode 1653. Minimum Deletions to Make String Balanced

문제

You are given a string s consisting only of characters 'a' and 'b'​​​​.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

• 모든 a가 b 앞에 오도록 문자열 s에서 문자를 제거할때
  최소한으로 제거한 수를 구하시오

예시

s 가 aababbab 일때
2번째 index의 b와 6번째 index의 a를 제거시 aaabbb 가 된다.
즉 2

제한

• $1 <= s.length <= 10^5$
• $s[i] == a$ or $s[i] == b$

풀이

• 특정 기준점을 중심으로 기준점 왼쪽에 b의 갯수와 기준점 오른쪽의 a의 갯수의 합이 최소가 될때 그 최솟값을 구하면 된다.
  • 즉 앞에 나오는 모든 b와 뒤에 나오는 a의 최솟값을 찾는다.
• 맨 앞에서부터 시작해서 변수 a는 문자열의 모든 a의 갯수, b는 0으로 해서 왼쪽부터 구한다.

class Solution:
    def minimumDeletions(self, s: str) -> int:
        b = 0
        a = s.count('a')
        
        # 왼쪽 구간 ( b가 제거 ) 이 아예 없을때 부터 시작한다.
        # 오른쪽 구간 ( 현재는 전체 문자열 ) 의 모든 a를 제거할때.
        ans = a

        for c in s:
        # 해당 문자열이 b일 경우 앞에 b가 나온다는 의미이기에 b에 1 뺀다.
        # 해당 문자열이 a일 경우 오른쪽 구간에 a가 1개 제외된다는 의미이기에 a를 뺀다.
            if c == 'b':
                b += 1
            else:
                a -= 1
		# 여기서 a + b는 왼쪽 구간의 b의 갯수 + 오른쪽 구간의 a의 갯수가 된다.
            ans = min(ans, a + b)

        return ans