目标
给你一个字符串 word 和一个整数 numFriends。
Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：
- word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
- 所有分割出的字符串都会被放入一个盒子中。
在所有回合结束后，找出盒子中 字典序最大的 字符串。
示例 1：
输入: word = "dbca", numFriends = 2
输出: "dbc"
解释:
所有可能的分割方式为：
"d" 和 "bca"。
"db" 和 "ca"。
"dbc" 和 "a"。示例 2：
输入: word = "gggg", numFriends = 4
输出: "g"
解释:
唯一可能的分割方式为："g", "g", "g", 和 "g"。提示:
- 1 <= word.length <= 5 * 10^3
- word 仅由小写英文字母组成。
- 1 <= numFriends <= word.length
思路
将 word 划分为 numFriends 个非空子串，求字典序最大的子串。
找字典序最大的首字母，如果存在多个需要比较后面字符的字典序，还要保证能够划分成非空子串。
先找到字符串中字典序最大的字符集合作为起点，将其后面的字符放入优先队列 [char, index]，根据字符从大到小排序，取队首连续相同的字符，将其后一个字符放到下一轮处理。
也可以不用手动逐个比较字符，枚举字典序最大的字符作为左端点，然后尽可能地扩展字符串长度 n - numFriends + 1，将结果收集后排序即可。
代码
/**
* @date 2025-06-04 9:19
*/
public class AnswerString3403 {
public String answerString(String word, int numFriends) {
if (numFriends == 1) {
return word;
}
int n = word.length();
List<Integer>[] chars = new ArrayList[26];
Arrays.setAll(chars, x -> new ArrayList<>());
for (int i = 0; i < n; i++) {
char c = word.charAt(i);
chars[c - 'a'].add(i);
}
int l = n - numFriends + 1;
String[] strs = null;
for (int i = 25; i >= 0; i--) {
if (chars[i].size() > 0) {
strs = new String[chars[i].size()];
for (int j = 0; j < chars[i].size(); j++) {
int index = chars[i].get(j);
strs[j] = word.substring(index, Math.min(index + l, n));
}
break;
}
}
Arrays.sort(strs);
return strs[strs.length - 1];
}
}
性能
