小鱼儿外贸建站,wordpress阅读量怎么查看,网络营销要怎么做,微信网站是多少钱一年文章目录1. 题目2. 解题1. 题目
给你一个字符串 s 和一个整数 repeatLimit #xff0c;用 s 中的字符构造一个新字符串 repeatLimitedString #xff0c;使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
返回 字典序最大的 repeatLimited…
文章目录1. 题目2. 解题1. 题目
给你一个字符串 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 由小写英文字母组成来源力扣LeetCode 链接https://leetcode-cn.com/problems/construct-string-with-repeat-limit 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
map 对字符计数map是有序的为了获得字典序最大逆序开始取每次判断字符串的末尾跟map最末尾的元素是否一样不一样就取最多 repeatLimit 次一样的话就取 倒数第二个 元素 1 次
class Solution {
public:string repeatLimitedString(string s, int repeatLimit) {mapchar,int m;for(auto c : s)m[c];string ans;while(!m.empty()){int ct repeatLimit;auto it m.end();it--; // 最后一个元素if(it-first ans.back()){ // ans最后的字符 跟 最大的字符 一样 if(it m.begin())break; // 没有第二大的字符了结束else{it--;// 有第二大的取一个出来就行了ans.push_back(it-first);if(--(it-second)0)m.erase(it);}}else{ // ans最后的字符 跟 最大的字符 不一样 while(ct !m.empty()){ans.push_back(it-first);if(--(it-second)0){m.erase(it);break;}ct--;}}}return ans;}
};104 ms 24 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
