构造限制重复的字符串 图解题解

这道题到底在问什么

输入

s="cczazcc", repeatLimit=3

输出

"zzcccac"

输入

s="aababab", repeatLimit=2

输出

"bbabaa"

先想最直接的笨办法

先数一遍 s 里每个字母出现几次:z 两个、c 四个、a 一个。右边这张小表就是词频桶,从大到小排好 z、c、a,记着各自还剩几个。左边七个方格是答案的位置,现在全空,我们要从最大的字母开始,一个一个把它们填满。（动画第 4 步）

最优解：一步一步想明白

1. 3记住这两句:先摆最大、一段至多 repeatLimit 个;放不下还剩就垫一个更小的字母隔开再续。下面一步步套用它。
2. 4先数一遍 s 里每个字母出现几次:z 两个、c 四个、a 一个。右边这张小表就是词频桶,从大到小排好 z、c、a,记着各自还剩几个。左边七个方格是答案的位置,现在全空,我们要从最大的字母开始,一个一个把它们填满。
3. 5为什么从最大字母下手?比较字典序是从左往右逐位看,谁在越靠前的位上放了更大的字母,谁就更大。所以贪心策略很直接:每一步都在还没放满的最靠前位置,填进当前还有剩的最大字母。此刻最大的是 z,就从 z 开始。
4. 6当前最大字母是 z。一段最多连放 repeatLimit 也就是 3 个,而 z 手头只有 2 个,取两者里小的,这一段就放 2 个 z。因为 2 没到 3,放完 z 正好用光,不需要隔板。开始往前两个空位填 z。
5. 7第一个 z 落到位置 0,这是整串的最高位,放上了最大的字母,开局就把字典序顶到最高。右边桶里 z 的剩余从 2 减到 1。这一段目前连续 1 个 z,绿色标出来的就是当前的连续段。
6. 8第二个 z 落到位置 1,z 的剩余减到 0,用光了。现在开头是连续两个 z,长度 2,没有超过限制 3,合法。绿色这段清楚地显示了这个连续的 z 段。z 既然摆完,下一步该找比它小的、还有剩的最大字母。
7. 9回头核对一下这段 z:连续 2 个,规则允许至多 3 个,稳稳合法。答案前两位已经锁定成 z z,这是任何合法串在这两位上能给到的最大字母了。z 用完,接下来看谁是还有剩的最大字母。
8. 10词频桶里 z 已经是 0,跳过它。往下看,c 还剩 4 个,是现在最大的可用字母。于是把当前处理对象切到 c。注意 c 有 4 个、限制才 3,这里就要遇到本题真正的看点:一段接不完,得想办法续。
9. 11轮到 c。一段最多连放 3 个,而 c 有 4 个,取小的,这一段先放 3 个 c。放的时候盯着:一旦连续凑满 3 个,就不能再直接接第 4 个 c 了。先把这 3 个 c 填进接下来的三个空位。
10. 12第一个 c 落到位置 2,c 的剩余从 4 减到 3。当前这段连续 c 的长度是 1。这一位为什么不接着放 z?因为 z 已经没有了,c 是现在能拿到的最大字母,放 c 就是这一位的最优选择。
11. 13第二个 c 落到位置 3,c 剩余减到 2。绿色的连续 c 段长度变成 2,还没到上限 3,可以再接一个。继续放第三个 c。
12. 14第三个 c 落到位置 4,连续 c 的长度到了 3,正好顶到上限。可 c 还剩 1 个没放。麻烦来了:下一位要是再放 c,连续就变成 4 个,超过限制 3,整串作废。所以这一位绝对不能再接 c。
13. 15设想一下硬接第四个 c:当前这段 c 会连成连续 4 个 c,直接违反至多 3 个的规则,这个串就不合法了。正确做法是先在中间垫一个比 c 小的字母当隔板,把连续的 c 断成两段,之后才能再接 c。下面去找这个隔板。
14. 16隔板不能随便选,为了尽量不拉低字典序,要挑比 c 小的字母里、当前还有剩的、最大的那一个。比 c 小的依次是 b、a。b 一个都没有,跳过;a 还剩 1 个,就用 a 当隔板。挑到了。
15. 17词频桶里 b 是 0,直接跳过;a 是 1,选中它。这里只放 1 个 a 就够了,隔板的作用是断开连续,用一个就能把前面的 c 段和后面要接的 c 段隔开,多放 a 反而挤占了后面本可以放 c 的位置,不划算。
16. 18把 a 放到位置 5,a 的剩余减到 0,用光了。现在答案末尾是 a,已经不是 c 了,连续的 c 被成功断开。绿色的当前段只剩这一个 a。隔板铺好,可以回头继续处理还剩 1 个的 c 了。
17. 19关键就在这一下:末尾变成了 a,再往后放 c,这个 c 前面紧挨的是 a 而不是 c,连续计数重新从 1 开始,不会触犯规则。隔板的价值就是这个断点。回到 c,看它还剩多少、这一段能放几个。
18. 20继续处理 c。它现在只剩 1 个,一段最多能放 3 个,取小的,这一段就放 1 个 c。放完 c 也就用光了。填到最后一个空位。
19. 21最后一个 c 落到位置 6,c 的剩余减到 0,也用光了。这一位的 c 紧挨着前面的 a,是新一段连续,长度只有 1,合法。七个位置全部填满,答案已经成形。
20. 22再看词频桶,z、c、a 的剩余全是 0,没有字母可放了,构造到此结束。七个位置从左到右读出来就是 zzcccac。因为每一步都在最靠前的位置放了当前能放的最大字母,整串的字典序就是最大的。
21. 23回放一遍最终串 zzcccac。逐段数连续长度:开头 z z 是 2,接着 c c c 是 3,然后 a 是 1,最后 c 是 1,每一段都不超过限制 3,完全合法。而且高位始终压着最大字母,所以它就是字典序最大的那个合法串,正是答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - ord("a")] += 1
        ans = []
        j = 24
        for i in range(25, -1, -1):
            j = min(i - 1, j)
            while 1:
                x = min(repeatLimit, cnt[i])
                cnt[i] -= x
                ans.append(ascii_lowercase[i] * x)
                if cnt[i] == 0:
                    break
                while j >= 0 and cnt[j] == 0:
                    j -= 1
                if j < 0:
                    break
                cnt[j] -= 1
                ans.append(ascii_lowercase[j])
        return "".join(ans)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
        }
        string ans;
        for (int i = 25, j = 24; ~i; --i) {
            j = min(j, i - 1);
            while (1) {
                for (int k = min(cnt[i], repeatLimit); k; --k) {
                    ans += 'a' + i;
                    --cnt[i];
                }
                if (cnt[i] == 0) {
                    break;
                }
                while (j >= 0 && cnt[j] == 0) {
                    --j;
                }
                if (j < 0) {
                    break;
                }
                ans += 'a' + j;
                --cnt[j];
            }
        }
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public String repeatLimitedString(String s, int repeatLimit) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 25, j = 24; i >= 0; --i) {
            j = Math.min(j, i - 1);
            while (true) {
                for (int k = Math.min(cnt[i], repeatLimit); k > 0; --k) {
                    ans.append((char) ('a' + i));
                    --cnt[i];
                }
                if (cnt[i] == 0) {
                    break;
                }
                while (j >= 0 && cnt[j] == 0) {
                    --j;
                }
                if (j < 0) {
                    break;
                }
                ans.append((char) ('a' + j));
                --cnt[j];
            }
        }
        return ans.toString();
    }
}

复杂度

面试官可能追问