文章目录
题目链接题目描述解题思路代码PythonJavaC++时空复杂度
华为OD算法/大厂面试高频题算法练习冲刺训练
题目链接
LeetCode2182、构建限制重复的字符串
题目描述
给你一个字符串 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 由小写英文字母组成
解题思路
为了使得构建的字符串ans字典序尽可能大，贪心地采取以下策略：
优先考虑剩余字符中最大的字符ch，若
ch剩余个数ch_num小于等于repeatLimit，则将这ch_num个ch都加入ans末尾ch剩余个数ch_num大于repeatLimit，则将repeatLimit个ch加入ans末尾，接下来必须再插入一个第二大的字符在ans末尾
字符的个数很容易想到用哈希表计数器进行统计。
由于总是要考虑最大的字符或次大的字符，而且一旦最大字符用完，在后续构建中都不能再考虑，很容易想到使用栈来维护上述过程。将细节处理好即可。
代码
Python
# 贪心+栈：O(N/repeatLimit)
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
# 统计s中每个元素的个数并按照字典序进行排序
stack = sorted([k, v] for k, v in Counter(s).items())
ans = str()
while len(stack) > 0:
# 考虑剩余最大字符ch
ch, ch_num = stack.pop()
# 如果ch的个数小于重复限制
if ch_num <= repeatLimit:
# 则将其全部加在末尾
ans += ch * ch_num
# 否则
else:
# 添加repeatLimit个ch在末尾
ans += ch * repeatLimit
# 如果此时还有其他字符存在，
# 则添加一个次大字符
if len(stack) > 0:
# 次大字符的个数-1
stack[-1][1] -= 1
# 在ans末尾添加1个次大字符
ans += stack[-1][0]
# 若次大字符的个数降为0，则也需要删除
if stack[-1][1] == 0:
stack.pop()
# 如果此时栈中已经没有其他字符
# 说明后面也无法再进行添加，直接退出
else:
break
# 将删除了repeatLimit个后的ch重新加入栈顶
stack.append([ch, ch_num - repeatLimit])
return ans
Java
class Solution {
public String repeatLimitedString(String s, int repeatLimit) {
Map
List
for (char ch : s.toCharArray()) {
charCount.put(ch, charCount.getOrDefault(ch, 0) + 1);
}
for (Map.Entry
stack.add(entry);
}
stack.sort(Comparator.comparing(Map.Entry::getKey));
StringBuilder ans = new StringBuilder();
while (!stack.isEmpty()) {
char ch = stack.get(stack.size() - 1).getKey();
int chNum = stack.get(stack.size() - 1).getValue();
stack.remove(stack.size() - 1);
if (chNum <= repeatLimit) {
ans.append(String.valueOf(ch).repeat(chNum));
} else {
ans.append(String.valueOf(ch).repeat(repeatLimit));
if (!stack.isEmpty()) {
stack.get(stack.size() - 1).setValue(stack.get(stack.size() - 1).getValue() - 1);
ans.append(stack.get(stack.size() - 1).getKey());
if (stack.get(stack.size() - 1).getValue() == 0) {
stack.remove(stack.size() - 1);
}
} else {
break;
}
stack.add(Map.entry(ch, chNum - repeatLimit));
}
}
return ans.toString();
}
}
C++
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
unordered_map
vector
for (char ch : s) {
charCount[ch]++;
}
for (const auto& entry : charCount) {
stack.push_back({entry.first, entry.second});
}
sort(stack.begin(), stack.end());
string ans;
while (!stack.empty()) {
char ch = stack.back().first;
int chNum = stack.back().second;
stack.pop_back();
if (chNum <= repeatLimit) {
ans += string(chNum, ch);
} else {
ans += string(repeatLimit, ch);
if (!stack.empty()) {
stack.back().second--;
ans += stack.back().first;
if (stack.back().second == 0) {
stack.pop_back();
}
} else {
break;
}
stack.push_back({ch, chNum - repeatLimit});
}
}
return ans;
}
};
时空复杂度
时间复杂度：O(N/repeatLimit)。循环大致需要进行N/repeatLimit次。
空间复杂度：O(1)。栈所占空间，最大为26，可视为常数级别空间。
华为OD算法/大厂面试高频题算法练习冲刺训练
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！ 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！ 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 & OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
相关文章
您阅读本篇文章共花了：
发表评论
2024-06-13 08:23:27回复