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.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 * 103word consists only of lowercase English letters.1 <= numFriends <= word.lengthclass Solution {
public String answerString(String word, int numFriends) {
if (numFriends == 1)
return word;
int n = word.length(), maxLen = n - numFriends + 1;
char startChar = word.charAt(0);
Set<Integer> startIdx = new HashSet<>();
for (int i = 0; i < n; i++) {
char c = word.charAt(i);
if (c > startChar) {
startIdx.clear();
startChar = c;
startIdx.add(i);
} else if (c == startChar)
startIdx.add(i);
}
String ans = "";
for (int i : startIdx) {
String w = word.substring(i, Math.min(i + maxLen, n));
System.out.println(w);
if (ans.compareTo(w) < 1)
ans = w;
}
return ans;
}
}