日期: 2025 年 6 月 4 日

目标

给你一个字符串 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];
    }

}

性能