---
# System prepended metadata

title: 2182. Construct String With Repeat Limit
tags: [Leetcode, Medium, Greedy]

---

# 2182. Construct String With Repeat Limit
###### tags: `Leetcode` `Medium` `Greedy`
Link:https://leetcode.com/problems/construct-string-with-repeat-limit/
## 思路 $O(N)$ $O(N)$
自己想到的
但是摘抄一下别人写的步骤
1. Count all characters in 26 buckets ('a' to 'z').
2. While we have characters left:
    - Find the largest bucket i that still has characters.
    - Take up to limit characters from bucket i.
    - Find the second largest bucket j that has characters.
    - Pick 1 character from bucket j.
## Code
```java=
class Solution {
    public String repeatLimitedString(String s, int repeatLimit) {
        int[] cnt = new int[26];
        for(int i=0; i<s.length(); i++){
            cnt[s.charAt(i)-'a']++;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=cnt.length-1; i>=0; i--){
            if(cnt[i]==0) continue;
            for(int j=0; j<Math.min(cnt[i], repeatLimit); j++) sb.append((char)(i+'a'));
            cnt[i] -= Math.min(cnt[i], repeatLimit);
            while(cnt[i]!=0){
                int p2 = i-1;
                while(p2>=0 && cnt[p2]==0) p2--;
                if(p2<0) return sb.toString();
                sb.append((char)(p2+'a'));
                cnt[p2]--;
                for(int j=0; j<Math.min(cnt[i], repeatLimit); j++) sb.append((char)(i+'a'));
                cnt[i] -= Math.min(cnt[i], repeatLimit);
            }
        }
        return sb.toString();
    }
}
```