Medium

题目描述

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

提示：

  • 找到从每个索引开始的长度不超过 n - numFriends + 1 的字典序最大子字符串。

解题思路

这道题的关键是理解分割的规律和找到最优策略。

解题思路

当我们将长度为 n 的字符串分割成 numFriends 段时，为了让某一段尽可能长（从而可能获得字典序更大的字符串），我们需要让其他段尽可能短。由于每段至少要有一个字符，所以某一段的最大长度为 n - numFriends + 1。

关键观察：

  1. 如果 numFriends = 1，整个字符串就是答案
  2. 否则，我们可以选择任意起始位置，然后取长度不超过 n - numFriends + 1 的子字符串
  3. 为了得到字典序最大的结果，我们需要遍历所有可能的起始位置

具体策略：

  • 对于每个可能的起始位置 i，我们可以取从位置 i 开始、长度为 min(maxLen, n - i) 的子字符串
  • 其中 maxLen = n - numFriends + 1
  • 在所有这些子字符串中选择字典序最大的

优化：我们可以先找到字符串中最大的字符，只考虑以该字符开头的子字符串，这样可以减少比较次数。

代码实现

class Solution {
public:
    string answerString(string word, int numFriends) {
        int n = word.length();
        if (numFriends == 1) {
            return word;
        }
        
        int maxLen = n - numFriends + 1;
        string result = "";
        
        // 找到最大字符
        char maxChar = *max_element(word.begin(), word.end());
        
        for (int i = 0; i < n; i++) {
            if (word[i] == maxChar) {
                int len = min(maxLen, n - i);
                string candidate = word.substr(i, len);
                if (candidate > result) {
                    result = candidate;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        n = len(word)
        if numFriends == 1:
            return word
        
        max_len = n - numFriends + 1
        result = ""
        
        # 找到最大字符
        max_char = max(word)
        
        for i in range(n):
            if word[i] == max_char:
                length = min(max_len, n - i)
                candidate = word[i:i + length]
                if candidate > result:
                    result = candidate
        
        return result

public class Solution {
    public string AnswerString(string word, int numFriends) {
        int n = word.Length;
        if (numFriends == 1) {
            return word;
        }
        
        int maxLen = n - numFriends + 1;
        string result = "";
        
        // 找到最大字符
        char maxChar = word.Max();
        
        for (int i = 0; i < n; i++) {
            if (word[i] == maxChar) {
                int len = Math.Min(maxLen, n - i);
                string candidate = word.Substring(i, len);
                if (string.Compare(candidate, result) > 0) {
                    result = candidate;
                }
            }
        }
        
        return result;
    }
}

var answerString = function(word, numFriends) {
    if (numFriends === 1) {
        return word;
    }
    
    const n = word.length;
    const maxLen = n - numFriends + 1;
    let result = "";
    
    for (let i = 0; i < n; i++) {
        const substring = word.substring(i, Math.min(i + maxLen, n));
        if (substring > result) {
            result = substring;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²)，其中 n 是字符串长度。需要遍历字符串找到最大字符的所有位置，对于每个位置可能需要O(n)时间进行字符串比较
空间复杂度O(n)，用于存储候选字符串和结果字符串

相关题目