LeetCode解法汇总2182. 构造限制重复的字符串

目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

描述：

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

解题思路：

这里字符串顺序和最终结果无关，所以我们可以使用长度为26的数组，记录每个字符出现的数量，方便后续使用。

可以使用递归的思路，构造一个方法负责拼接字符串。传入值为当前最大的字符位置，然后进行循环，每次选择补充repeatLimit数量的当前剩余最大字符和次大字符，如果补充成功，则继续，否则跳出循环。

当所有字符串都补充完整后，结果就是最终补充完整的字符串。

代码：

class Solution2182
{
public:
    string outStr = "";
    string repeatLimitedString(string s, int repeatLimit)
    {

        vector<int> nums(26);
        const char *c = s.c_str();
        while (*c != '\0')
        {
            char currentChar = *c;
            nums[currentChar - 'a']++;
            c++;
        }

        int index = 25;
        while (index >= 0)
        {
            if (nums[index] == 0)
            {
                index--;
                continue;
            }
            int nextIndex = repeatLimitedOneChar(nums, repeatLimit, index);
            index = nextIndex;
        }
        return outStr;
    }

    int repeatLimitedOneChar(vector<int> &nums, int repeatLimit, int index)
    {
        int nextIndex = index - 1;
        while (nums[index] > 0)
        {
            int num = min(repeatLimit, nums[index]);
            for (int i = 0; i < num; i++)
            {
                outStr += (char)('a' + index);
            }
            nums[index] -= num;
            if (nums[index] == 0 || index == 0)
            {
                break;
            }
            while (nextIndex >= 0 && nums[nextIndex] == 0)
            {
                nextIndex--;
            }
            if (nextIndex < 0)
            {
                return nextIndex;
            }
            outStr += (char)('a' + nextIndex);
            nums[nextIndex] -= 1;
        }
        return nextIndex;
    }
};