LC 2182.Construct String With Repeat Limit

题目描述

这是 LeetCode 上的 2182. 构造限制重复的字符串 ，难度为简单。

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

解答

方法一：贪心 + 双指针

先统计字符串 s 中各个字符的数量，用双指针模拟填入的过程，从字符集的末尾开始遍历，如果填入的字符没有超过限制 repeatLimit 则继续填入，如果超过则填入接下来的一个字符，然后如果之前的还有剩下字符，则继续填入，否则继续填入下一个字符。

class Solution {
    public static int N = 26;
    public String repeatLimitedString(String s, int repeatLimit) {
        int[] ch = new int[N];
        for (int i = 0; i < s.length(); ++i) {
            ++ch[s.charAt(i) - 'a'];
        }
        StringBuffer sb = new StringBuffer();
        int cnt = 0;
        for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
             if (ch[i] == 0) { // 当前字符用完，填入后面的字符，更新cnt
                 cnt = 0;
                 --i;
             } else if (cnt < repeatLimit) { // 当前字符未超过限制
                 sb.append((char) (i + 'a'));
                 ++cnt;
                 --ch[i];
             } else if (j >= i || ch[j] == 0) { // 当前字符已经超过限制，查找下一个字符
                 --j;
             } else { // 当前字符超过限制，填入下一个字符，更新cnt
                 cnt = 0;
                 sb.append((char) (j + 'a'));
                 --ch[j];
             }
        }
        return sb.toString();
    }
}

• 时间复杂度：\(O(N + M)\)，其中 N 为 s 的长度， M = 26 为字符集的大小。

• 空间复杂度：\(O(M)\)，M 为字符集的大小。

每题一图