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

题目

https://leetcode.cn/problems/construct-string-with-repeat-limit/description/

解答

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        vector<int> vec(26);
        for (char c : s) {
            ++vec[c-'a'];
        }
        string res;
        int cnt = 0;
        for (int i = 'z' - 'a', j = i - 1; i >= 0 && j >= 0;) {
            if (vec[i] == 0) {
                --i;
                cnt = 0;
            }
            else if (cnt < repeatLimit) {
                res += (i + 'a');
                --vec[i];
                ++cnt;
            }
            else if (j >= i || vec[j] == 0) {
                --j;
            }
            else {
                res += (j + 'a');
                --vec[j];
                cnt = 0;
            }
        }
        return res;
    }
};

测试主函数

int main() {
    string s = "cczazcc";
    int repeatLimit = 3;
    Solution sol;
    cout<<sol.repeatLimitedString(s, repeatLimit);
	return 0;
}

解释

1. 初始化和字符计数

vector<int> count(N);
for (char c : s) {
    count[c - 'a']++;
}

在这一部分中，首先定义了一个大小为 N（26）的 count 向量，用于统计字符串 s 中每个小写字母的出现次数。通过 c - 'a' 计算字符 c 在字母表中的索引，并在 count 向量中相应位置递增计数。

2. 构建结果字符串

string ret;
int m = 0;
for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
    // ...
}

这部分代码初始化了结果字符串 ret 和一个变量 m（用于追踪当前字符的连续出现次数）。接着，使用两个循环变量 i 和 j 进行遍历。i 从 N - 1（即字母 ‘z’）开始向下迭代，寻找可用的最大字母。j 从 N - 2（即字母 ‘y’）开始，用于在当前字母达到重复限制时找到下一个可用字母。

3. 字符填充逻辑

if (count[i] == 0) {
    m = 0;
    i--;
} else if (m < repeatLimit) {
    count[i]--;
    ret.push_back('a' + i);
    m++;
} else if (j >= i || count[j] == 0) {
    j--;
} else {
    count[j]--;
    ret.push_back('a' + j);
    m = 0;
}

这是函数的核心逻辑：

• 当前字符用完：如果 count[i] 为 0（即当前字母用完了），重置 m 并让 i 指向下一个字母。
• 当前字符未达重复限制：如果 m < repeatLimit，添加当前字母到 ret，更新 count[i] 和 m。
• 寻找备选字符：如果当前字符达到重复限制，检查 j 是否有可用字符。如果没有，将 j 向前移动。
• 使用备选字符：如果有可用的备选字符，将其添加到 ret 中，更新 count[j] 并重置 m。

4. 返回结果

return ret;

循环结束后，返回构建的字符串 ret，它是按照题目要求，尽可能使用字母表中较大的字符构建的，且每个字符的连续出现次数不超过 repeatLimit。

总结

这个函数的目标是重新构建字符串，使得任何字符在新字符串中连续出现的次数不超过 repeatLimit，同时尽可能保持字符在字母表中的降序。它通过维护每个字符的出现次数以及重复限制来实现这一目标，并在必要时使用备选字符填充。