【LeetCode每日一题】2182. 构造限制重复的字符串

本文主要是介绍【LeetCode每日一题】2182. 构造限制重复的字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024-1-13

文章目录

- - [2182. 构造限制重复的字符串](https://leetcode.cn/problems/construct-string-with-repeat-limit/)
  - - - 思路：

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

思路：

按照字符出现次数从高到低的顺序进行重复，通过维护一个指针 j 来寻找下一个非零出现次数的字母。同时，利用 StringBuilder 对象可以高效地构建字符串，避免频繁的字符串拼接操作

首先，创建一个长度为26的数组 cnt，用于统计字符串 s 中每个字符出现的次数。数组的下标对应字母表中的字母，通过 s.charAt(i) - 'a' 可以得到字符在字母表中的位置，然后将对应位置的计数器加1。
创建一个 StringBuilder 对象 ans，用于构建最终结果。
从字母表的最后一个字母 ‘z’ 开始，依次处理每个字母。同时维护一个指针 j，初始值为当前字母的前一个字母下标 i-1。
进入一个循环，直到当前字母的出现次数为0。在循环中，主要进行以下操作：
- 将当前字母重复的次数与限制次数 repeatLimit 取较小值，设为变量 k。使用 for 循环遍历 k 次，将当前字母添加到 ans 中，并将字母的计数器减1。
- 如果当前字母的出现次数为0，则跳出内部循环。
- 在内部循环中，需要寻找下一个非零出现次数的字母，即从 j 开始向前搜索。如果找到了下一个字母（即 j >= 0 并且 cnt[j] != 0），则将其添加到 ans 中，并将该字母的计数器减1。
- 如果找不到下一个字母，则跳出外部循环。
最终，返回 ans 构建的字符串作为结果。

    public String repeatLimitedString(String s, int repeatLimit) {// 创建一个长度为26的数组，用于统计字符串s中每个字符出现的次数int[] cnt = new int[26];for (int i = 0; i < s.length(); ++i) {++cnt[s.charAt(i) - 'a'];}// 创建一个StringBuilder对象，用于构建最终结果StringBuilder ans = new StringBuilder();// 遍历字母表，从后往前依次处理每个字母for (int i = 25, j = 24; i >= 0; --i) {// j表示当前字母的前一个字母下标，初始值为i-1j = Math.min(j, i - 1);// 循环直到当前字母的出现次数为0while (true) {// 将当前字母重复的次数与限制次数取较小值，进行遍历并添加到结果中for (int k = Math.min(cnt[i], repeatLimit); k > 0; --k) {ans.append((char) ('a' + i));--cnt[i];}// 如果当前字母的出现次数为0，则跳出循环if (cnt[i] == 0) {break;}// 寻找下一个非零出现次数的字母while (j >= 0 && cnt[j] == 0) {--j;}// 如果找不到下一个字母，则跳出循环if (j < 0) {break;}// 将下一个字母添加到结果中，并将其出现次数减1ans.append((char) ('a' + j));--cnt[j];}}// 返回最终结果return ans.toString();}