最长快乐字符串 图解题解
这道题到底在问什么
- 输入
- a=1, b=1, c=7
- 输出
- ccaccbcc
- 输入
- a=2, b=2, c=1
- 输出
- ababc
- 输入
- a=0, b=0, c=1
- 输出
- c
最优解：一步一步想明白
- 3记牢两句:优先放剩余最多的字母;但末尾已经两个相同时就跳过它、改放次多的。下面每一位都在套这两句。
- 4上面这排是要拼的串,现在全是占位点 ·,一位都还没填。右边面板是三个字母的剩余可用次数:a 有 1 个,b 有 1 个,c 有 7 个。c 明显最多。接下来从最左边开始,每一位都贪心地挑剩余最多、又不会凑成三连的字母填进去。
- 5填第一位。三个字母按剩余次数从多到少排:c 有 7、a 有 1、b 有 1。c 最多,而且串还空着,放 c 不会三连,就先拿 c。
- 6把 c 填进第 0 位,亮起来的就是它。c 的剩余次数从 7 减到 6。现在串是 "c"。继续看下一位。
- 7填第 1 位。眼下剩余排序是 c 有 6 个、a 有 1 个、b 有 1 个。剩最多的是 c,先看它放进去会不会三连。
- 8把 c 填进第 1 位,亮起来的就是它。c 的剩余次数从 6 减到 5。现在串是 "cc"。继续看下一位。
- 9填第 2 位。眼下剩余排序是 c 有 5 个、a 有 1 个、b 有 1 个。剩最多的是 c,可是要先看末尾会不会三连。
- 10注意看末尾标红的两位,都是 c。c 虽然剩得最多,可这会儿再放一个就会凑成 ccc,犯规。所以这一位跳过 c,往后挑剩余次多、又不会三连的字母,也就是 a,它还剩 1 个。
- 11把 a 填进第 2 位,亮起来的就是它。a 的剩余次数从 1 减到 0。现在串是 "cca",a 已经用光了。继续看下一位。
- 12填第 3 位。眼下剩余排序是 c 有 5 个、b 有 1 个、a 有 0 个。剩最多的是 c,先看它放进去会不会三连。
- 13把 c 填进第 3 位,亮起来的就是它。c 的剩余次数从 5 减到 4。现在串是 "ccac"。继续看下一位。
- 14填第 4 位。眼下剩余排序是 c 有 4 个、b 有 1 个、a 有 0 个。剩最多的是 c,先看它放进去会不会三连。
- 15把 c 填进第 4 位,亮起来的就是它。c 的剩余次数从 4 减到 3。现在串是 "ccacc"。继续看下一位。
- 16填第 5 位。眼下剩余排序是 c 有 3 个、b 有 1 个、a 有 0 个。剩最多的是 c,可是要先看末尾会不会三连。
- 17注意看末尾标红的两位,都是 c。c 虽然剩得最多,可这会儿再放一个就会凑成 ccc,犯规。所以这一位跳过 c,往后挑剩余次多、又不会三连的字母,也就是 b,它还剩 1 个。
- 18把 b 填进第 5 位,亮起来的就是它。b 的剩余次数从 1 减到 0。现在串是 "ccaccb",b 已经用光了。继续看下一位。
- 19填第 6 位。眼下剩余排序是 c 有 3 个、a 有 0 个、b 有 0 个。剩最多的是 c,先看它放进去会不会三连。
- 20把 c 填进第 6 位,亮起来的就是它。c 的剩余次数从 3 减到 2。现在串是 "ccaccbc"。继续看下一位。
- 21填第 7 位。眼下剩余排序是 c 有 2 个、a 有 0 个、b 有 0 个。剩最多的是 c,先看它放进去会不会三连。
- 22把 c 填进第 7 位,亮起来的就是它。c 的剩余次数从 2 减到 1。现在串是 "ccaccbcc"。继续看下一位。
- 23填第 8 位。眼下剩余排序是 c 有 1 个、a 有 0 个、b 有 0 个。剩最多的是 c,可是要先看末尾会不会三连。
- 24到这一步,串末尾是 cc,只有 c 还剩 1 个,可再放一个 c 就会凑成三连,不行;a 和 b 都已经用光。三个字母谁都放不进去,贪心结束。这就是题目说的「用不下就剩着」,最后这 1 个 c 没能用上。拼好的串是 "ccaccbcc"。
- 25从左拼到右,贪心每一位都挑剩余最多、又不致三连的字母,中途两次因为末尾两个 c 而跳过 c、改放 a 和 b 把它们隔开。最后拼出 "ccaccbcc",长度 8,里面没有任何三连,这就是最长的快乐字符串,跟开头说的答案对上了。
⚠️ 容易写错的地方
✗ 错：不管三连,每次都死放剩余最多的字母
✓ 对：放最多的之前先看末尾两位是不是已经是它,会三连就跳过、改放次多的
贪心放最多没错,但少了三连这道刹车就会拼出 ccc 这种非法串。像 c 连放两个后,第三位必须先用别的字母把它隔开,否则犯规
✗ 错：以为必须把 a,b,c 全部用完才算对
✓ 对：能放就放、放不下就停,剩下的字母直接丢掉
当某个字母数量远超另两个时根本塞不下。比如 a=1,b=1,c=7,c 最多只能放下 6 个(每两个 c 之间得垫一个别的字母),剩的那 1 个 c 注定用不上,答案长度是 8 不是 9
✗ 错：把刹车条件写成「末尾一个相同就跳过」
✓ 对：是末尾连续两个都相同才跳过,只有一个相同还能再放一个
允许两个连续相同,只是不许三个。末尾是单个 c 时再放一个 c 得到 cc 是合法的,只有已经是 cc 时放第三个才犯规;条件写松成「一个就跳」会拼不长
完整代码（Python / C++ / Java）
Python
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 longestDiverseString(self, a: int, b: int, c: int) -> str:
counts = {"a": a, "b": b, "c": c}
ans = []
while True:
picked = None
for ch in sorted(counts, key=lambda x: (-counts[x], x)):
if counts[ch] == 0:
continue
if len(ans) >= 2 and ans[-1] == ans[-2] == ch:
continue
picked = ch
break
if picked is None:
break
ans.append(picked)
counts[picked] -= 1
return "".join(ans)C++
#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 longestDiverseString(int a, int b, int c) {
vector<pair<char, int>> cnt = {{'a', a}, {'b', b}, {'c', c}};
string ans;
while (true) {
sort(cnt.begin(), cnt.end(), [](auto& x, auto& y) {
if (x.second != y.second) return x.second > y.second;
return x.first < y.first;
});
int pick = -1;
for (int i = 0; i < 3; ++i) {
char ch = cnt[i].first;
if (cnt[i].second == 0) continue;
int n = ans.size();
if (n >= 2 && ans[n - 1] == ch && ans[n - 2] == ch) continue;
pick = i;
break;
}
if (pick < 0) break;
ans.push_back(cnt[pick].first);
--cnt[pick].second;
}
return ans;
}
};Java
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 longestDiverseString(int a, int b, int c) {
int[] cnt = {a, b, c};
char[] chars = {'a', 'b', 'c'};
StringBuilder ans = new StringBuilder();
while (true) {
Integer[] order = {0, 1, 2};
Arrays.sort(order, (i, j) -> cnt[i] != cnt[j] ? cnt[j] - cnt[i] : chars[i] - chars[j]);
int pick = -1;
for (int idx : order) {
if (cnt[idx] == 0) continue;
int n = ans.length();
if (n >= 2 && ans.charAt(n - 1) == chars[idx] && ans.charAt(n - 2) == chars[idx]) continue;
pick = idx;
break;
}
if (pick < 0) break;
ans.append(chars[pick]);
cnt[pick]--;
}
return ans.toString();
}
}复杂度
时间
O(n)
n = a+b+c 是答案最长可能长度。每放一个字母做一轮:排序的只是 a,b,c 三个元素,是常数;挑字母也只扫这三个。总共最多放 n 个字母,所以是线性的 O(n)。注:若推广到 k 种字母用大顶堆维护,则是 O(n log k),本题 k 固定为 3 故为常数因子
空间
O(n)
按峰值算,主要是存答案那个字符串或 StringBuilder,长度最多 n,占 O(n)。除答案之外只用了三个计数和固定几个变量,是常数 O(1);所以不计输出时是 O(1),计输出则 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最长快乐字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么每一位要贪心地放剩余最多的字母,而不是放最少的?+
因为剩得最多的字母最危险,它最容易在后面堆成三连把自己卡死。越早、越频繁地把它往外匀,它就越不容易在末尾连续撞上三连;要是先把少的放完,多的那个最后只剩它一种,连续放就必然三连、放不下去,反而拼得更短。所以优先消化最多的,再用次多的去隔开,整体能拼到最长。
答案为什么可能用不完所有字母,什么时候会剩?+
当某个字母的数量超过另外两个之和能提供的「间隔位」时就会剩。每两个相同字母之间必须垫一个别的,设最多的那个有 m 个、其余共 r 个,那么最多能放下 2 乘 r 加 2 个该字母;超过这个数的部分注定塞不进去,只能剩着。比如 a=1,b=1,c=7,其余只有 2 个,c 最多放 6 个,剩 1 个 c 用不上,答案长度 8。
如果不是三种字母,而是任意多种字母,这套贪心还成立吗,复杂度怎么变?+
思路一样:每一位放当前剩余最多、且不会和末尾凑成三连的字母。区别在于字母多了,不能每轮都把全部排一遍,通常改用一个大顶堆按剩余次数维护:弹出堆顶,如果它正好会三连就先弹第二个来放、再把堆顶压回去。这样每放一个字母是 O(log k),k 是字母种类数,总复杂度 O(n log k)。本题 k 固定是 3,排三个元素是常数,所以退化成 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最长快乐字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。