README.md

2182. 构造限制重复的字符串

English Version

题目描述

给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。

返回 字典序最大的 repeatLimitedString 。

如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。

 

示例 1：

输入：s = "cczazcc", repeatLimit = 3
输出："zzcccac"
解释：使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "zzcccac" 。
注意，尽管 "zzcccca" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。

示例 2：

输入：s = "aababab", repeatLimit = 2
输出："bbabaa"
解释：
使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。 
字母 'a' 连续出现至多 2 次。 
字母 'b' 连续出现至多 2 次。 
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。 
该字符串是字典序最大的 repeatLimitedString ，所以返回 "bbabaa" 。 
注意，尽管 "bbabaaa" 字典序更大，但字母 'a' 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。

 

提示：

• 1 <= repeatLimit <= s.length <= 105
• s 由小写英文字母组成

解法

方法一：贪心 + 双指针

Python3

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - ord('a')] += 1
        ans = []
        for i in range(25, -1, -1):
            j = i - 1
            while 1:
                for _ in range(min(repeatLimit, cnt[i])):
                    cnt[i] -= 1
                    ans.append(chr(ord('a') + i))
                if cnt[i] == 0:
                    break
                while j >= 0 and cnt[j] == 0:
                    j -= 1
                if j < 0:
                    break
                cnt[j] -= 1
                ans.append(chr(ord('a') + j))
        return ''.join(ans)

Java

class Solution {
    public String repeatLimitedString(String s, int repeatLimit) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 25; i >= 0; --i) {
            int j = i - 1;
            while (true) {
                for (int k = Math.min(repeatLimit, cnt[i]); k > 0; --k) {
                    cnt[i]--;
                    ans.append((char) ('a' + i));
                }
                if (cnt[i] == 0) {
                    break;
                }
                while (j >= 0 && cnt[j] == 0) {
                    --j;
                }
                if (j < 0) {
                    break;
                }
                cnt[j]--;
                ans.append((char) ('a' + j));
            }
        }
        return ans.toString();
    }
}

C++

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        vector<int> cnt(26);
        for (char& c : s) cnt[c - 'a']++;
        string ans;
        for (int i = 25; ~i; --i) {
            int j = i - 1;
            while (true) {
                for (int k = min(cnt[i], repeatLimit); k; --k) {
                    cnt[i]--;
                    ans.push_back('a' + i);
                }
                if (cnt[i] == 0) break;
                while (~j && cnt[j] == 0) --j;
                if (j < 0) break;
                cnt[j]--;
                ans.push_back('a' + j);
            }
        }
        return ans;
    }
};

Go

func repeatLimitedString(s string, repeatLimit int) string {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[c-'a']++
	}
	var ans []byte
	for i := 25; i >= 0; i-- {
		j := i - 1
		for {
			for k := min(cnt[i], repeatLimit); k > 0; k-- {
				cnt[i]--
				ans = append(ans, 'a'+byte(i))
			}
			if cnt[i] == 0 {
				break
			}
			for j >= 0 && cnt[j] == 0 {
				j--
			}
			if j < 0 {
				break
			}
			cnt[j]--
			ans = append(ans, 'a'+byte(j))
		}
	}
	return string(ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

TypeScript

...