[LeetCode] 2182. Construct String With Repeat Limit (Python)

 

난이도: 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.

 

문제 예제

---

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa".
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

 

 

제한 사항

---

• 1 <= repeatLimit <= s.length <= 10^5
• s consists of lowercase English letters.

 

✏️ Solution(솔루션)

---

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        count_s = Counter(s)
        alpha = sorted(count_s.keys(), reverse = True)
        n = len(alpha)

        answer = ""

        for i in range(n):
            check_limit = 0
            
            while count_s[alpha[i]] != 0:
                answer += alpha[i]
                count_s[alpha[i]] -= 1
                check_limit+=1
                
                if check_limit == repeatLimit and count_s[alpha[i]] > 0:
                    check = False
                    for j in range(i+1, n):
                        if count_s[alpha[j]] != 0:
                            answer += alpha[j]
                            count_s[alpha[j]] -= 1
                            check = True
                            break
                    if not check: 
                        break
                    check_limit = 0
        
        return answer

 

이 문제도 heapq를 사용하는 문제 같았지만, 최근 heapq로만 문제를 풀고 있는 것 같아 새로운 방법으로 풀어보았다.

 

일단 나는 Greedy하게 접근했다.

 

제일 큰 알파벳을 가능한 한 먼저 사용해 최대한 사전 순으로 큰 문자열을 만들면 되지 않을까 생각하여, Counter를 통해 각 알파벳의 갯수를 저장했다.

 

그리고 제일 큰 알파벳 부터 갯수가 0이 될때까지 answer에다가 + 해주었다.

 

하지만 이 때 +해주던 알파벳이 repeatLimit만큼 반복되었을 때, 계속 +할 수 없으니 그 다음으로 큰 알파벳을 찾아 answer에 +해주었다.

 

예를 들어, 다음과 같다.

 

인풋이 다음과 같을 때: s = "cczazcc", repeatLimit = 3 제일 큰 알파벳부터 answer에 추가해준다

 

1. answer = z

2. answer = zz

 

제일 큰 알파벳의 갯수가 0이 되었으니 다음으로 큰 알파벳으로 넘어간다.

 

3. answer = zzc

4. answer = zzcc

5. answer = zzccc

 

이때 c의 갯수가 하나 남았지만 이미 repeatLimit만큼 반복되었기 때문에 그 다음으로 큰 알파벳을 +한다.

만약 그 다음으로 큰 알파벳이 없다면 여기서 반복을 종료하고 answer를 return하면 된다.

 

6. answer = zzccca

 

그리고 다시 c가 0이 될 때까지 반복한다.

 

7. answer = zzcccac

 

이제 모든 알파벳을 소모했기 때문에 이를 반환하여 정답을 맞출 수 있었다.

 

 

다 풀고 Runtime을 확인해보니 효율적인 방법은 아닌 것 같다.. heapq를 사용했을때보다 2배 정도 차이가 나는 것 같다.

 

Heapq를 이용한 풀이

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        count_s = Counter(s)
        hq = [(-ord(k), v) for k,v in count_s.items()]
        heapq.heapify(hq)

        answer = ""

        while hq:
            current_alpha, cnt = heapq.heappop(hq)
            answer += chr(-current_alpha) * min(repeatLimit, cnt)

            if cnt > repeatLimit and hq:
                next_alpha, next_cnt = heapq.heappop(hq)
                answer += chr(-next_alpha)
                if next_cnt > 1:
                    heapq.heappush(hq, (next_alpha, next_cnt - 1))
                heapq.heappush(hq, (current_alpha, cnt-repeatLimit))

        return answer

 

---

2182. Construct String With Repeat Limit