[LeetCode] 3403. Find the Lexicographically Largest String From the Box I

You are given a string word, and an integer numFriends.

Alice is organizing a game for her numFriends friends. There are multiple rounds in the game, where in each round:

word is split into numFriends non-empty strings, such that no previous round has had the exact same split.
All the split words are put into a box.
Find the lexicographically largest string from the box after all the rounds are finished.

Example 1:
Input: word = “dbca”, numFriends = 2
Output: “dbc”

Explanation:
All possible splits are:
“d” and “bca”.
“db” and “ca”.
“dbc” and “a”.

Example 2:
Input: word = “gggg”, numFriends = 4
Output: “g”

Explanation:
The only possible split is: “g”, “g”, “g”, and “g”.

Constraints:
1 <= word.length <= 5 * 103
word consists only of lowercase English letters.
1 <= numFriends <= word.length

从盒子中找出字典序最大的字符串 I。

给你一个字符串 word 和一个整数 numFriends。

Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：

word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。

所有分割出的字符串都会被放入一个盒子中。

在所有回合结束后，找出盒子中 字典序最大的 字符串。

思路

这道题不涉及算法，就是比较字符串的字典序大小。既然是找字典序最大的字符串，那么肯定是越长越好。但是这个字符串的长度也是有一个上限的，因为需要确保剩下的字符串的长度足够再分给 numFriends - 1 个朋友。

所以具体的做法是，我们从 0 开始遍历 input 字符串，对于每个位置 i，我们尝试找到一个子串 [i, i + k)，这个子串的长度需要满足

• i + k <= word.length, 意思是子串不能越界
• word.length - (i + k) >= numFriends - 1, 意思是剩下的字符串长度足够分给其他朋友

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public String answerString(String word, int numFriends) {
        // corner case
        if (numFriends == 1) {
            return word;
        }

        // normal case
        int n = word.length();
        String res = "";
        for (int i = 0; i < n; i++) {
            int k = Math.min(n - i, n - numFriends + 1);
            String cur = word.substring(i, i + k);
            if (cur.compareTo(res) > 0) {
                res = cur;
            }
        }
        return res;
    }
}