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

🟠 🔖 贪心 哈希表 字符串 计数 堆（优先队列） 🔗 力扣open in new window LeetCodeopen in new window

题目

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 _thelexicographically 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.

Constraints:

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

题目大意

给你一个字符串 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 <= 10^5
s 由小写英文字母组成

解题思路

统计频次并排序：
- 使用 count[26] 数组记录 s 中每个字符的出现次数
从高到低处理字符：
- 每次选择字典序最大的字符，添加到结果字符串中，且连续添加次数不超过 repeatLimit。
- 如果当前字符无法继续使用（因为会超出限制），则选择字典序次大的字符插入。
- 插入次靠后的字符后，可以重新尝试使用当前最靠后的字符。
- 若没有其他字符可以插入，则停止构造。
结束条件：
- 当所有字符的频次都被用完时，退出循环，返回构造好的字符串。

复杂度分析

时间复杂度：O(n)，其中 n 是输入字符串的长度。
- 统计频次需要 O(n)。
- 每次寻找可用字符需要 O(26)（常数）。
- 构造结果字符串需要遍历所有字符，总计 O(n)。
- 总复杂度为 O(n)。
空间复杂度：O(n)，使用一个 res 数组储存结果字符，最坏情况下会存储 n 个字符。

代码

/**
 * @param {string} s
 * @param {number} repeatLimit
 * @return {string}
 */
var repeatLimitedString = function (s, repeatLimit) {
	const getChar = (i) => String.fromCharCode('a'.charCodeAt() + i);
	// 统计每个字符的频次
	let count = new Array(26).fill(0);
	for (let char of s) {
		count[char.charCodeAt() - 'a'.charCodeAt()]++;
	}

	// 标记是否还有更大的字符没有用完
	let lastIdx = -1;
	let res = [];
	for (let i = 25; i >= 0; i--) {
		// 找到第一个可以用的字符
		if (count[i] == 0) {
			continue;
		}

		// 如果还有更大的字符没用完，说明是超过重复限制了，插入次大字符一次，再接着插入更大的字符
		if (lastIdx > 0) {
			// 插入次大字符一次
			res.push(getChar(i));
			count[i]--;
			// 因为每次循环后会 i--，所以让 i = lastIdx + 1，保证下次进入循环时 i 是 lastIdx
			i = lastIdx + 1;
			lastIdx = -1;
		} else {
			// 插入当前字符，最多插入 repeatLimit 次
			for (let j = 0; j < repeatLimit && count[i] > 0; j++, count[i]--) {
				res.push(getChar(i));
			}
			if (count[i] > 0) {
				// 标记当前字符还没有用完
				lastIdx = i;
			}
		}
	}
	return res.join('');
};

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

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

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目