建设网站是否等于开展网络营销,微信公众号开发网站开发,php网页开发,深圳计算机软件培训学校3妹#xff1a;“太阳当空照#xff0c;花儿对我笑#xff0c;小鸟说早早早#xff0c;你为什么背上炸药包” 2哥 :3妹#xff0c;什么事呀这么开森。 3妹#xff1a;2哥你看今天的天气多好啊#xff0c;最近一周都是大晴天#xff0c;艳阳高照 2哥#xff1a;是啊“太阳当空照花儿对我笑小鸟说早早早你为什么背上炸药包” 2哥 :3妹什么事呀这么开森。 3妹2哥你看今天的天气多好啊最近一周都是大晴天艳阳高照 2哥是啊天气不冷不热的很适合生活 3妹据说南方的小土豆都跑到北方滑雪了哈哈哈哈 2哥泼水成冰好玩是好玩但是一定要注意防寒哦看新闻都有人冻伤了。 3妹是啊还是待在室内比较好 2哥给你出了一道题发你微信里了 上班通勤的路上记得看一下回来问你答案~ 3妹知道啦难不倒我
题目
给你一个字符串 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 由小写英文字母组成
思路 贪心 双指针,
我们可以按照如下的方式构造字符串这样构造出的字符串对应的字典序一定是最大的
每次选择当前剩余的字典序最大的字符加到字符串末尾如果字符串末尾的字符已经连续出现了 repeatLimit 次则将字典序次大的字符加到字符串末尾随后继续选择当前剩余的字典序最大的字符加到字符串末尾直至使用完字符或没有新的字符可以合法加入。
java代码
class Solution {static public int N 26;public String repeatLimitedString(String s, int repeatLimit) {int[] count new int[N];for (int i 0; i s.length(); i) {count[s.charAt(i) - a];}StringBuilder ret new StringBuilder();int m 0;for (int i N - 1, j N - 2; i 0 j 0;) {if (count[i] 0) { // 当前字符已经填完填入后面的字符重置 mm 0;i--;} else if (m repeatLimit) { // 当前字符未超过限制count[i]--;ret.append((char)(a i));m;} else if (j i || count[j] 0) { // 当前字符已经超过限制查找可填入的其他字符j--;} else { // 当前字符已经超过限制填入其他字符并且重置 mcount[j]--;ret.append((char)(a j));m 0;}}return ret.toString();}
}
