[LeetCode] 3223. Minimum Length of String After Operations

https://leetcode.com/problems/minimum-length-of-string-after-operations/description/

leetcode - Minimum Length of String After Operations

문제 유형: 문자열 처리, 그리디

문제 난이도: Medium

 

문제

You are given a string s.

You can perform the following process on s any number of times:

• Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].
• Delete the closest character to the left of index i that is equal to s[i].
• Delete the closest character to the right of index i that is equal to s[i].

Return the minimum length of the final string s that you can achieve.

 

문자열 s가 주어집니다.

다음의 연산을 몇 번이고 할 수 있습니다:

s[i]의 문자와 같은 문자가 왼쪽 prefix, 오른쪽 suffix에 있다면, 그 왼쪽과 오른쪽에 있는 문자를 없앨 수 있다.

 

문자열을 최소길이로 변환시킨 길이를 구하시오.

 

풀이

최대한 없앤 것이 최적해이다.

각 문자별로 빈도를 저장한다.

이제, 각 26개의 글자를 확인하면서, 다음을 확인한다:

홀수라면, 연산을 최대한 많이 적용시 1개가 남는다.

짝수이고 2개이상인 경우, 2개가 남는다.

이를 이용해서 문자 개수들을 더해 최종 길이를 빠르게 구할 수 있다.

 

코드

C++

class Solution {
public:
    int minimumLength(string s) {
        vector<int> freq(26, 0);
        for(const auto &ch : s) {
            freq[ch-'a']++;
        }

        int ans = 0;
        for(int i = 0; i < 26; ++i) {
            if(freq[i]%2==1) ans++;
            else if(freq[i] >=2) ans += 2;
        }

        return ans;
    }
};