江阴网络推广公司_免费考研论坛_软文写作要求_网站优化推广公司排名

题意

一段字符串可以分割成numFriends份，每一份满足不为空，求其中最大的 Lexicographically Largest String是什么字符串

题目链接

https://leetcode.com/problems/find-the-lexicographically-largest-string-from-the-box-i/description/

思考

首先对于同一个起始位置的字符串而言，字符串越长，Lexicographically越大。由于每一份字符串不为空，所以字符串的长度是有个最大值的

题解

枚举起始位置，对于每一个起始位置而言，Lexicographically最大的字符串的长度是(word.size() - numFriends + 1)和(n-i+1)的较小值。记录每个起始位置的字符串并且比较

class Solution {
public:string answerString(string word, int numFriends) {if (numFriends == 1) {return word;}int n = word.size();int len = n - numFriends + 1;string res = word.substr(0, len);for(int i = 0; i < n; i++) {string t = word.substr(i, min(len, n - i + 1));if( t > res) {res = t;}}return res;}
};

时间复杂度: $O(n^2)$ 截取字符串是$O(n)$
空间复杂度: $O(1)$