构造具有重复限制的字符串

2182。构造具有重复限制的字符串

难度：中等

主题：哈希表、字符串、贪婪、堆（优先级队列）、计数

给定一个字符串 s 和一个整数 RepeatLimit。使用 s 的字符构造一个新字符串repeatLimitedString，使得字母不会连续出现超过重复限制次数连续。您不必必须使用 s 中的所有字符。

返回字典中最大的可能的repeatLimitedString。

如果在 a 和 b 不同的第一个位置，字符串 a 的字母在字母表中出现的字母晚于 b 中对应的字母，则字符串 a 按字典顺序 大于字符串 b。如果前 min(a.length, b.length) 个字符没有不同，则较长的字符串是字典顺序上较大的字符串。

示例1：

• 输入： s = "cczazcc"，repeatLimit = 3
• 输出：“zzcccac”
• 解释：我们使用 s 中的所有字符来构造重复限制字符串“zzcccac”。
  • 字母“a”最多连续出现 1 次。
  • 字母“c”最多连续出现 3 次。
  • 字母“z”最多连续出现 2 次。
  • 因此，连续出现的字母不会超过repeatLimit 次，并且该字符串是有效的repeatLimitedString。
  • 该字符串是字典中可能的最大的重复限制字符串，因此我们返回“zzcccac”。
  • 请注意，字符串“zzcccca”按字典顺序更大，但字母“c”连续出现超过 3 次，因此它不是有效的重复限制字符串。

示例2：

• 输入： s = “aababab”，repeatLimit = 2
• 输出：“bbabaa”
• 解释：我们仅使用 s 中的部分字符来构造重复限制字符串“bbabaa”。
  • 字母“a”最多连续出现2次。
  • 字母“b”最多连续出现 2 次。
  • 因此，连续出现的字母不会超过repeatLimit 次，并且该字符串是有效的repeatLimitedString。
  • 该字符串是字典中可能的最大的重复限制字符串，因此我们返回“bbabaa”。
  • 请注意，字符串“bbabaaa”按字典顺序更大，但字母“a”连续出现超过 2 次，因此它不是有效的 RepeatLimitedString。

约束：

• 1 5
• s 由小写英文字母组成。

提示：

1. 开始按字符降序构造字符串。
2. 当达到repeatLimit时，选择下一个最大的字符。

解决方案：

我们使用贪婪方法来优先考虑字典顺序上较大的字符，同时确保没有字符连续超过repeatLimit。该方法使用优先级队列（最大堆）按字典顺序降序处理字符，并确保没有字符连续出现超过repeatLimit次数。

解决方案说明

1. 统计字符：使用数组统计字符串s中每个字符出现的频率。
2. 最大堆：使用最大堆（优先级队列）按字典顺序降序排序和提取字符。
3. 贪婪构造：
   • 添加最大可用字符，最多重复限制次数。
   • 如果达到当前字符的repeatLimit，则切换到下一个最大的字符，插入一次，然后将第一个字符重新插入堆中以供进一步使用。
4. 边缘处理：当角色无法进一步使用时进行适当管理。

让我们用 PHP 实现这个解决方案：2182。构造具有重复限制的字符串

<?php
/**
 * @param String $s
 * @param Integer $repeatLimit
 * @return String
 */
function repeatLimitedString($s, $repeatLimit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>

解释：

1. 频率计数：

   • 迭代字符串 s 以计算每个字符的出现次数。
   • 将频率存储在关联数组 $freq 中。

2. 降序排序：

   • 使用 krsort() 按字符的字典顺序按降序顺序对字符进行排序。

3. 构建结果：

   • 将字典顺序最大的字符（$char）连续追加到结果字符串中。
   • 如果某个字符达到其重复限制，请暂时停止追加它。
   • 使用临时队列来保存仍有剩余计数但暂时跳过的字符。

4. 处理重复限制：

   • 如果当前字符已达到重复限制，则使用队列中按字典顺序排列的下一个最大字符。
   • 将前一个字符重新插入到频率图中以便稍后继续处理。

5. 边缘情况：

   • 角色最初可能不会用完其全部计数。
   • 处理完队列中的备份字符后，当前字符将恢复处理。

如何运作

1. 字符计数：$freq 跟踪所有字符的出现次数。
2. 最大堆：SplPriorityQueue 用作最大堆，其中字符按其 ASCII 值（降序）排列优先级。
3. 字符串构造：
   • 如果当前字符已达到其重复限制，则获取下一个最大的字符。
   • 使用下一个最大的字符一次，并将前一个字符恢复到堆中以供将来使用。
4. 最终结果：结果字符串是满足repeatLimit约束的字典顺序最大的字符串。

示例演练

输入：

s = "cczazcc", 重复限制 = 3

步骤：

1. 频率计数：
   
   ['a'=> 1、'c' => 4、'z' => 2]

2. 降序排列：
   
   ['z'=>; 2、'c' => 4、'a' => 1]

3. 在遵守重复限制的同时附加字符：

   • 追加“z”→“zz”（z 计数 = 0）
   • 追加“c”3次→“zzccc”（c计数= 1）
   • 追加“a”→“zzccca”（计数 = 0）
   • 追加剩余的“c”→“zzcccac”

输出：“zzcccac”

时间复杂度

• 字符频率计数：O(n)，其中n是字符串的长度。
• 堆操作：O(26 log 26)，因为堆最多可以容纳 26 个字符。
• 总体复杂度：O(n 26 log 26) ≈ O(n).

空间复杂度

• O(26) 频率数组。
• O(26) 堆。

测试用例

<?php
/**
 * @param String $s
 * @param Integer $repeatLimit
 * @return String
 */
function repeatLimitedString($s, $repeatLimit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */

}

// Test Cases
echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac
echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa
?>

边缘情况

1. s 仅包含一个唯一字符（例如，“aaaaaaa”，repeatLimit = 2）：输出将仅包含连续允许的字符数。
2. RepeatLimit = 1：输出在可用字符之间交替。
3. s 中的所有字符都是唯一的：输出按降序排序。

此实现在限制范围内有效工作。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是构造具有重复限制的字符串的详细内容。更多信息请关注PHP中文网其他相关文章！