跳转至

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

题目描述

给你一个字符串 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 * 103
  • word 仅由小写英文字母组成。
  • 1 <= numFriends <= word.length

解法

方法一：枚举子串左端点

如果我们固定子字符串的左端点，那么子字符串越长，字典序越大。假设子字符串左端点为 \(i\)，剩余子字符串的最小长度为 \(\text{numFriends} - 1\)，那么子字符串的右端点可以取到 \(\min(n, i + n - (\text{numFriends} - 1))\)，其中 \(n\) 为字符串的长度。注意我们说的是左开右闭。

我们枚举所有可能的左端点，取出对应的子字符串，比较字典序，最终得到字典序最大的子字符串。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为字符串的长度。

1
2
3
4
5
6
class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        if numFriends == 1:
            return word
        n = len(word)
        return max(word[i : i + n - (numFriends - 1)] for i in range(n))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        int n = word.length();
        String ans = "";
        for (int i = 0; i < n; ++i) {
            String t = word.substring(i, Math.min(n, i + n - (numFriends - 1)));
            if (ans.compareTo(t) < 0) {
                ans = t;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    string answerString(string word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        int n = word.length();
        string ans = "";
        for (int i = 0; i < n; ++i) {
            string t = word.substr(i, min(n - i, n - (numFriends - 1)));
            if (ans < t) {
                ans = t;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func answerString(word string, numFriends int) (ans string) {
    if numFriends == 1 {
        return word
    }
    n := len(word)
    for i := 0; i < n; i++ {
        t := word[i:min(n, i+n-(numFriends-1))]
        ans = max(ans, t)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function answerString(word: string, numFriends: number): string {
    if (numFriends === 1) {
        return word;
    }
    const n = word.length;
    let ans = '';
    for (let i = 0; i < n; i++) {
        const t = word.slice(i, Math.min(n, i + n - (numFriends - 1)));
        ans = t > ans ? t : ans;
    }
    return ans;
}

评论