[LeetCode] 1653. Minimum Deletions to Make String Balanced

 

https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/description/?envType=daily-question&envId=2024-07-30

leetcode - Minimum Deletions to Make String Balanced

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

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가 주어진다.

모든 b가 a 뒤에 나오도록 balanced된 문자열을 만들기 위해서, 필요한 최소 제거 수를 구하시오.

 

풀이

문자열 s를 순회하면서,

b를 만나면 b의 개수를 누적한다.

a를 만나면, a를 삭제하는 것과 이전의 b들을 삭제하는 경우, 둘 중 하나를 선택한다.

 

bbab의 경우,

b : bCount = 1, ans = 0(이미 balanced)

bb : bCount = 2, ans = 0(이미 balanced)

bba : bCount = 2, ans = 1(ans + 1, 즉 a를 삭제함)

bbab: bCount = 3, ans = ans = 1(bba에서 a를 삭제한 balanced 문자열에다가 그냥 b를 추가한 경우의 수)

 

 

코드

C++

class Solution {
public:
    int minimumDeletions(string s) {
        int bCount = 0;
        int ans = 0;

        for(const char &ch : s) {
            if(ch == 'b') bCount++;
            else if(ch == 'a') {
                ans = min(ans+1, bCount);
            }
        }

        return ans;
    }
};