[LeetCode] 2516. Take K of Each Character From Left and Right

https://leetcode.com/problems/take-k-of-each-character-from-left-and-right/description/?envType=daily-question&envId=2024-11-20

leetcode - Take K of Each Character From Left and Right

문제 유형: 슬라이딩 윈도우

문제 난이도: Medium

 

문제

You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

 

'a', 'b', 'c'로만 이루어진 문자열 s가 있다.

음이아닌 정수 k도 주어진다.

각 분마다, 당신은 가장 s의 가장 왼쪽 또는 가장 오른쪽 문자를 가져갈 수 있다.

각 문자를 최소 k개 챙기는 최소 시간을 구하시오.

 

풀이

왼쪽에서 몇 개 가져갈지를 고르면, 오른쪽에서는 최소 몇 개를 챙겨야 하는지가 정해진다.

그림에서의 금색 부분이 보존될 부분, 빨간색이 왼쪽에서 챙기는 부분, 파란색이 오른쪽에서 최소 챙겨야 하는 부분이다.

 

슬라이딩 윈도우로 각 알파벳의 개수를 센다. 이는 처음에 모두 챙긴다는 의미이다.

세주고 난 뒤에는 윈도우의 크기를 줄여볼 것이다.

 

left를 n-1에서 줄여가면서, 윈도우의 크기를 줄인다. right도 n-1로 초기화한다.

그러다가 각 요소의 개수가 하나라도 k개보다 작아지면, right도 왼쪽으로 밀면서 다시 추가한다.

이는 left의 범위를 줄이다가 조건이 안맞으면, 제거된 뒷부분부터 right에 다시 넣는 것을 의미한다.

크기를 매번 업데이트한다.

 

최종 크기를 반환한다.

 

코드

C++

class Solution {
public:
    int takeCharacters(string s, int k) {
        int ca = 0;
        int cb = 0;
        int cc = 0;
        int n = s.size();

        for(char ch : s) {
            if(ch == 'a') ca++;
            else if(ch == 'b') cb++;
            else cc++;
        } 

        if(ca < k || cb < k || cc < k) return -1;

        int ans = n;
        int left = n-1, right = n-1;
        while(left >= 0) {
            char ch = s[left];
            if(ch == 'a') ca--;
            else if(ch == 'b') cb--;
            else cc--;

            while(right >= left && (ca < k || cb < k || cc < k)) {
                ch = s[right];
                if(ch == 'a') ca++;
                else if(ch == 'b') cb++;
                else cc++;
                right--;
            }

            ans = min(ans, left - 1 + n - right);
            left--;
        }
        return ans;
    }
};