Medium

题目描述

给你一个字符串 s 和一个整数 repeatLimit ，请你构造一个新字符串 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 由小写英文字母组成

解题思路

这是一道贪心算法题，核心思路是尽可能构造字典序最大的字符串。

解题思路：

为了得到字典序最大的字符串，我们应该优先使用字母表中较后的字符。基本策略如下：

  1. 字符统计：首先统计字符串中每个字符的出现次数
  2. 贪心构造：从字典序最大的字符开始，尽可能多地添加该字符（不超过repeatLimit）
  3. 间隔处理：当某个字符达到连续使用上限时，插入一个次大的字符作为间隔，然后继续使用最大字符

具体算法：

  • 使用计数数组统计每个字符的频次
  • 使用两个指针，一个指向当前最大的可用字符，一个指向次大的字符
  • 当最大字符用完repeatLimit次后，插入一个次大字符，然后继续使用最大字符
  • 如果次大字符不存在或用完，则移动到下一个最大字符

时间复杂度分析：

  • 统计字符：O(n)
  • 构造字符串：O(n)，每个字符最多被访问常数次
  • 总体时间复杂度：O(n)

这种方法既保证了字典序最大，又满足了重复限制的要求。

代码实现

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        string result;
        int i = 25; // 从最大字符开始
        
        while (i >= 0) {
            if (count[i] == 0) {
                i--;
                continue;
            }
            
            // 添加当前最大字符，最多repeatLimit个
            int use = min(count[i], repeatLimit);
            for (int j = 0; j < use; j++) {
                result += (char)('a' + i);
            }
            count[i] -= use;
            
            // 如果还有剩余的当前字符，需要插入一个次大字符
            if (count[i] > 0) {
                int next = i - 1;
                while (next >= 0 && count[next] == 0) {
                    next--;
                }
                
                if (next < 0) break; // 没有其他字符可用
                
                result += (char)('a' + next);
                count[next]--;
            }
        }
        
        return result;
    }
};

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        result = []
        i = 25  # 从最大字符开始
        
        while i >= 0:
            if count[i] == 0:
                i -= 1
                continue
            
            # 添加当前最大字符，最多repeatLimit个
            use = min(count[i], repeatLimit)
            result.extend([chr(ord('a') + i)] * use)
            count[i] -= use
            
            # 如果还有剩余的当前字符，需要插入一个次大字符
            if count[i] > 0:
                next_char = i - 1
                while next_char >= 0 and count[next_char] == 0:
                    next_char -= 1
                
                if next_char < 0:
                    break  # 没有其他字符可用
                
                result.append(chr(ord('a') + next_char))
                count[next_char] -= 1
        
        return ''.join(result)

public class Solution {
    public string RepeatLimitedString(string s, int repeatLimit) {
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        StringBuilder result = new StringBuilder();
        int i = 25; // 从最大字符开始
        
        while (i >= 0) {
            if (count[i] == 0) {
                i--;
                continue;
            }
            
            // 添加当前最大字符，最多repeatLimit个
            int use = Math.Min(count[i], repeatLimit);
            for (int j = 0; j < use; j++) {
                result.Append((char)('a' + i));
            }
            count[i] -= use;
            
            // 如果还有剩余的当前字符，需要插入一个次大字符
            if (count[i] > 0) {
                int next = i - 1;
                while (next >= 0 && count[next] == 0) {
                    next--;
                }
                
                if (next < 0) break; // 没有其他字符可用
                
                result.Append((char)('a' + next));
                count[next]--;
            }
        }
        
        return result.ToString();
    }
}

var repeatLimitedString = function(s, repeatLimit) {
    const count = new Array(26).fill(0);
    for (const c of s) {
        count[c.charCodeAt(0) - 97]++;
    }
    
    const result = [];
    let i = 25; // 从最大字符开始
    
    while (i >= 0) {
        if (count[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
最优解法O(n)O(1)

说明：

  • 时间复杂度： O(n)，其中 n 是字符串 s 的长度。我们需要遍历一次字符串统计字符频次，然后构造结果字符串时每个字符最多被处理常数次
  • 空间复杂度： O(1)，只使用了固定大小的计数数组（26个字母）和常数额外空间，不计算输出字符串的空间

相关题目