[LeetCode] 2182. Construct String With Repeat Limit

https://leetcode.com/problems/construct-string-with-repeat-limit/description/

leetcode - Construct String With Repeat Limit

문제 유형: 우선순위 큐, 그리디, 문자열 처리

문제 난이도: Medium

 

문제

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

 

문자열 s와 정수 repeatLimit을 받는다.

재구성해서 repeatLimitedString을 만들어라.

같은 글자가 연속해서 repeatLimit이하여야 한다.

이러한 문자열들 중에서 가장 사전순으로 뒤에오는 것을 만드시오.

 

풀이

사전순으로 뒤이려면, 알파벳이 뒤쪽일수록 좋다.

즉, prefix가 뒤쪽 알파벳으로 최대한 채워져야 한다.

최대한 큰 알파벳부터 앞쪽에 연속적으로 붙이는걸 우선순위 큐로 할 수 있다.

pq에서 꺼내서 min(남은알파벳개수, repeatLimit)개만큼 붙이고, 개수를 줄인걸 반영해서 다시 pq에 넣는다.

만약 현재 생성중인 문자열의 맨 뒤가 이번 pq의 톱과 같다면, 후순위의 글자를 하나 붙여준다. 남은 후순위글자가 없다면, 생성을 멈춘다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

struct comp {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
        return a.first < b.first;
    }
};

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

        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
        for(int i = 0; i < 26; ++i) {
            if(freq[i] > 0) pq.push({i + 'a', freq[i]});
        }

        string res = "";
        while(!pq.empty()) {
            auto x = pq.top();
            int ch = x.first;
            int cnt = x.second;
            pq.pop();

            if(res.empty() || res[res.size()-1] != ch) {
                int k = min(repeatLimit, cnt);
                for(int i = 0; i < k; ++i) {
                    res += (char)ch;
                }
                cnt -= k;
                if(cnt > 0) pq.push({ch, cnt}); 
            } else if(!pq.empty()) {
                auto y = pq.top();
                int ch2 = y.first;
                int cnt2 = y.second;
                pq.pop();
                
                res += (char)ch2;
                cnt2 -= 1;

                pq.push({ch, cnt}); 
                if(cnt2 > 0) pq.push({ch2, cnt2});
            } else break;
        }
        return res;
    }
};