1653. Minimum Deletions to Make String Balanced

[zeikar]

Problem link

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

Problem Summary

a 또는 b를 최소한으로 지워서 문자열을 /a*b*/ 형태로 만드는 횟수를 구하는 문제.

Solution

기준점을 두고 그리디하게 왼쪽의 b를 지우고 오른쪽의 a를 지웠을 때 횟수의 합 중 최소를 구하면 된다.

마지막에 1 빼주는건 현재 위치가 중복으로 들어가서 그냥 빼주었다. (현재 위치도 카운트에 집어넣었기 때문)

또한, 배열을 안쓰고 count 변수 2개로도 풀 수 있긴 하다. 공간복잡도도 내려가지만 일단 처음 제출한 코드로 포스트는 쓰는걸로..

Source Code

class Solution:
    def minimumDeletions(self, s: str) -> int:
        deleteA = [0] * len(s)
        deleteAcnt = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == 'a':
                deleteAcnt += 1
            deleteA[i] = deleteAcnt
        
        deleteB = [0] * len(s)
        deleteBcnt = 0
        for i in range(len(s)):
            if s[i] == 'b':
                deleteBcnt += 1        
            deleteB[i] = deleteBcnt

        ans = float('inf')
        for i in range(len(s)):
            ans = min(ans, deleteA[i] + deleteB[i] - 1)
        return ans