Problem#
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.
Examples#
Example 1:
1
2
3
4
5
6
7
|
Input: word = "dbca", numFriends = 2
Output: "dbc"
Explanation:
All possible splits are:
* `"d"` and `"bca"`.
* `"db"` and `"ca"`.
* `"dbc"` and `"a"`.
|
Example 2:
1
2
3
4
|
Input: word = "gggg", numFriends = 4
Output: "g"
Explanation:
The only possible split is: `"g"`, `"g"`, `"g"`, and `"g"`.
|
Constraints#
1 <= word.length <= 5 * 10^3
word
consists only of lowercase English letters.
1 <= numFriends <= word.length
Solution#
Method 1 – Enumeration of All Splits#
We need to find the lexicographically largest substring that can result from splitting word
into numFriends
non-empty parts.
Lexicographical order is the same as dictionary order: for example, “bc” > “ab” because “b” comes after “a”, and “abcd” > “abc” since it has an extra character at the end.
This means we should look for the longest possible substring after making the required splits.
Since the string is divided into numFriends
parts, the longest substring possible is of length word.length() - numFriends + 1
.
To solve this, we can check all substrings of lengths from 1 up to word.length() - numFriends + 1
and return the largest one in lexicographical order.
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
string answerString(string word, int numFriends) {
if (numFriends == 1) return word;
int n = word.size();
string ans = "";
int maxLen = n - numFriends + 1;
for (int i = 0; i < n; ++i) {
string sub;
if (i + maxLen <= n)
sub = word.substr(i, maxLen);
else
sub = word.substr(i);
if (sub > ans)
ans = sub;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
type Solution struct{}
func (Solution) AnswerString(word string, numFriends int) string {
if numFriends == 1 {
return word
}
n := len(word)
ans := ""
maxLen := n - numFriends + 1
for i := 0; i < n; i++ {
var sub string
if i+maxLen <= n {
sub = word[i : i+maxLen]
} else {
sub = word[i:]
}
if sub > ans {
ans = sub
}
}
return ans
}
|
Java#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public String answerString(String word, int numFriends) {
if (numFriends == 1) return word;
int n = word.length();
String ans = "";
int maxLen = n - numFriends + 1;
for (int i = 0; i < n; i++) {
String sub;
if (i + maxLen <= n)
sub = word.substring(i, i + maxLen);
else
sub = word.substring(i);
if (sub.compareTo(ans) > 0)
ans = sub;
}
return ans;
}
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
fun answerString(word: String, numFriends: Int): String {
if (numFriends == 1) return word
val n = word.length
var ans = ""
val maxLen = n - numFriends + 1
for (i in 0 until n) {
val sub = if (i + maxLen <= n) word.substring(i, i + maxLen) else word.substring(i)
if (sub > ans) ans = sub
}
return ans
}
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def answerString(self, word: str, numFriends: int) -> str:
if numFriends == 1:
return word
n = len(word)
ans = ""
maxLen = n - numFriends + 1
for i in range(n):
if i + maxLen <= n:
sub = word[i:i+maxLen]
else:
sub = word[i:]
if sub > ans:
ans = sub
return ans
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
impl Solution {
pub fn answer_string(word: String, num_friends: i32) -> String {
if num_friends == 1 {
return word;
}
let n = word.len();
let max_len = n - num_friends as usize + 1;
let bytes = word.as_bytes();
let mut ans = "";
for i in 0..n {
let end = if i + max_len <= n { i + max_len } else { n };
let sub = &word[i..end];
if sub > ans {
ans = sub;
}
}
ans.to_string()
}
}
|
Complexity#
- ⏰ Time complexity:
O(n * maxLen)
, - where n
= length of word
and maxLen
= word.length() - numFriends + 1
(the length of the substring window)
- For each of the n starting indices, you extract a substring of up to
maxLen
and compare it to the current answer.
- In the worst case, substring extraction and comparison is O(maxLen) per iteration.
- So, overall time complexity:
O(n × (n - numFriends + 1))
For large
numFriends
, this approaches O(n); for small numFriends
, it approaches O(n²).
- 🧺 Space complexity:
O(n)
- O(maxLen) for storing the current substring and answer.
- No extra data structures are used that grow with input size.
- Overall space complexity:
O(n) (since maxLen ≤ n)