3403. Find the Lexicographically Largest String From the Box I LeetCode Solution
In this guide, you will get 3403. Find the Lexicographically Largest String From the Box I LeetCode Solution with the best time and space complexity. The solution to Find the Lexicographically Largest String From the Box I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Lexicographically Largest String From the Box I
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.
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 * 103
word consists only of lowercase English letters.
1 <= numFriends <= word.length
3403. Find the Lexicographically Largest String From the Box I LeetCode Solution in C++
class Solution {
public:
string answerString(string word, int numFriends) {
if (numFriends == 1)
return word;
const string s = lastSubstring(word);
const size_t sz = word.length() - numFriends + 1;
return s.substr(0, min(s.length(), sz));
}
private:
// Same as 1163. Last Substring in Lexicographical Order
string lastSubstring(string s) {
int i = 0;
int j = 1;
int k = 0;
while (j + k < s.length())
if (s[i + k] == s[j + k]) {
++k;
} else if (s[i + k] > s[j + k]) {
// Skip s[j..j + k) and advance to s[j + k + 1] to find a possible
// lexicographically larger substring since s[i..i + k) == s[j..j + k)
// and s[i + k] > s[j + k).
j = j + k + 1;
k = 0;
} else {
// Skip s[i..i + k) and advance to s[i + k + 1] or s[j] to find a
// possible lexicographically larger substring since
// s[i..i + k) == s[j..j + k) and s[i + k] < s[j + k).
// Note that it's unnecessary to explore s[i + k + 1..j) if
// i + k + 1 < j since they are already explored by j.
i = max(i + k + 1, j);
j = i + 1;
k = 0;
}
return s.substr(i);
}
}; /* code provided by PROGIEZ */
3403. Find the Lexicographically Largest String From the Box I LeetCode Solution in Java
class Solution {
public String answerString(String word, int numFriends) {
if (numFriends == 1)
return word;
final String s = lastSubstring(word);
final int sz = word.length() - numFriends + 1;
return s.substring(0, Math.min(s.length(), sz));
}
// Same as 1163. Last Substring in Lexicographical Order
private String lastSubstring(String s) {
int i = 0;
int j = 1;
int k = 0; // the number of the same letters of s[i..n) and s[j..n)
while (j + k < s.length())
if (s.charAt(i + k) == s.charAt(j + k)) {
++k;
} else if (s.charAt(i + k) > s.charAt(j + k)) {
// Skip s[j..j + k) and advance to s[j + k + 1] to find a possible
// lexicographically larger substring since s[i..i + k) == s[j..j + k)
// and s[i + k] > s[j + k).
j = j + k + 1;
k = 0;
} else {
// Skip s[i..i + k) and advance to s[i + k + 1] or s[j] to find a
// possible lexicographically larger substring since
// s[i..i + k) == s[j..j + k) and s[i + k] < s[j + k).
// Note that it's unnecessary to explore s[i + k + 1..j) if
// i + k + 1 < j since they are already explored by j.
i = Math.max(i + k + 1, j);
j = i + 1;
k = 0;
}
return s.substring(i);
}
} // code provided by PROGIEZ
3403. Find the Lexicographically Largest String From the Box I LeetCode Solution in Python
class Solution:
def answerString(self, word: str, numFriends: int) -> str:
if numFriends == 1:
return word
s = self._lastSubstring(word)
sz = len(word) - numFriends + 1
return s[:min(len(s), sz)]
# Same as 1163. Last Substring in Lexicographical Order
def _lastSubstring(self, s: str) -> str:
i = 0
j = 1
k = 0 # the number of the same letters of s[i..n) and s[j..n)
while j + k < len(s):
if s[i + k] == s[j + k]:
k += 1
elif s[i + k] > s[j + k]:
# Skip s[j..j + k) and advance to s[j + k + 1] to find a possible
# lexicographically larger substring since s[i..i + k) == s[j..j + k)
# and s[i + k] > s[j + k).
j = j + k + 1
k = 0
else:
# Skip s[i..i + k) and advance to s[i + k + 1] or s[j] to find a
# possible lexicographically larger substring since
# s[i..i + k) == s[j..j + k) and s[i + k] < s[j + k).
# Note that it's unnecessary to explore s[i + k + 1..j) if
# i + k + 1 < j since they are already explored by j.
i = max(i + k + 1, j)
j = i + 1
k = 0
return s[i:] # code by PROGIEZ
