# 最大字典序无重复串

# 解题思路

贪心思路

为了保证字典序最大，我们优先放置字母 b，然后再放置字母 a。在放置字符时，我们还需注意不能超过连续 k 次相同字符：

如果当前已经连续放置了 k 次相同字符，必须切换到另一个字符。
每次放置字符后，相应的字符数量减少，同时更新当前字符的连续计数。

实现步骤：

初始化：根据输入的 x, y, k 值，检查是否有可能构造出满足条件的字符串。初始化结果字符串的大小，并设置初始计数器。
循环放置字符：
- 优先放置字符 b，如果 b 的数量已经足够，或者已经放置了 k 次字符 b，则放置字符 a。
- 如果已经放置了 k 次相同字符，则强制切换到另一个字符。

C++代码如下：

#include<iostream>
#include<string>
using namespace std;

int main() {
    int countA, countB, maxRepeat;
    cin >> countA >> countB >> maxRepeat;

    // 检查是否有可能生成满足条件的字符串
    if (countA > (countB + 1) * maxRepeat || countB > (countA + 1) * maxRepeat) {
        cout << -1 << endl;
        return 0;
    }

    string result(countA + countB, ' ');  // 预先分配字符串大小
    int currentA = 0, currentB = 0;       // 当前连续 'a' 和 'b' 的计数
    int pos = 0;                          // 当前填充位置

    while (countA > 0 || countB > 0) {
        // 当可以继续添加 'a' 或 'b' 且没有超过最大连续限制时
        if (currentA < maxRepeat && currentB < maxRepeat) {
            if (countA <= countB * maxRepeat) {
                result[pos++] = 'b';
                countB--;
                currentB++;
                currentA = 0;
            } else {
                result[pos++] = 'a';
                countA--;
                currentA++;
                currentB = 0;
            }
        }

        // 当当前字符达到最大连续限制时，切换到另一个字符
        if (currentA == maxRepeat || currentB == maxRepeat) {
            if (result[pos - 1] == 'a') {
                result[pos++] = 'b';
                countB--;
                currentB = 1;
                currentA = 0;
            } else {
                result[pos++] = 'a';
                countA--;
                currentA = 1;
                currentB = 0;
            }
        }
    }

    cout << result << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

时间复杂度：O(n)