# LeetCode 2182. Construct String With Repeat Limit

## 題目大意

給定一個字串 `s` 和一個整數 `repeatLimit`
使用 `s` 中的字符構造一個新的字串 `repeatLimitedString`，要求同一個字母在字串中連續出現的次數不得超過 `repeatLimit`
你可以選擇不使用 `s` 中的所有字符

請返回字典序最大的 `repeatLimitedString`

## 思考

這題顯然還是 greedy

想法呢就是先想辦法挑大的
以下面的 C++ code 為例，我們從 `z` 開始挑 (`cnt[25]` 表示其數量)
只要數量不為 `0` 就先挑到連續的上限 (`repeatLimit`) 接著挑一個次大的 (`cnt[next]`) 一個就好，因為我們要想辦法接著繼續挑當前最大的，這樣字典順序才會最大

貪婪策略嘛，限制一解除當然就是要繼續最貪的作法

C++ 參考解答：

class Solution
{
public:
    string repeatLimitedString(string s, int repeatLimit)
    {
        int cnt[26] = {};

        for (const char &c : s)
        {
            ++cnt[c - 'a'];
        }

        string ans;
        ans.reserve(s.length());
        int prev = -1;

        for (int i = 25; i >= 0;)
        {
            if (!cnt[i])
            {
                --i;
                continue;
            }

            if (prev == i)
            {
                int next = i - 1;
                while (next >= 0 && !cnt[next])
                    --next;

                if (next < 0)
                    break;

                ans.push_back('a' + next);
                --cnt[next];
                prev = next;
            }
            else
            {
                const int appendCnt = min(cnt[i], repeatLimit);
                ans.append(appendCnt, 'a' + i);
                cnt[i] -= appendCnt;
                prev = i;
            }
        }

        return ans;
    }
};

Go 參考解答：

func repeatLimitedString(s string, repeatLimit int) string {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}

	ans := make([]byte, 0, len(s))
	prev := -1

	for i := 25; i >= 0; {
		if cnt[i] == 0 {
			i--
			continue
		}

		if prev == i {
			next := i - 1
			for next >= 0 && cnt[next] == 0 {
				next--
			}

			if next < 0 {
				break
			}

			ans = append(ans, byte('a'+next))
			cnt[next]--
			prev = next
		} else {
			appendCnt := min(cnt[i], repeatLimit)
			ans = append(ans, bytes.Repeat([]byte{byte('a' + i)}, appendCnt)...)
			cnt[i] -= appendCnt
			prev = i
		}
	}

	return string(ans)
}