Find the Lexicographically Largest String From the Box I Solution
Find the Lexicographically Largest String From the Box I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Lexicographically Largest String From the Box I is a medium coding problem on strings, two pointers and enumeration, asked in Google interviews.
- Difficulty: Medium
- Topics: Strings, Two Pointers, Enumeration
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string word and an integer numFriends.
A game is played over several rounds. In each round word is cut into exactly numFriends non-empty pieces, in a way that no earlier round used, and every piece is put into a box. The rounds continue until every possible split has been used once.
Return the lexicographically largest string in the box after all rounds.
Example 1
Input: word = "dbca", numFriends = 2
Output: dbc
Explanation: The splits are d|bca, db|ca and dbc|a; the largest piece is "dbc".
Example 2
Input: word = "gggg", numFriends = 4
Output: g
Explanation: The only split cuts the word into four "g" pieces.
Example 3
Input: word = "abc", numFriends = 1
Output: abc
Explanation: With one friend the only piece is the whole word.
Constraints
1 <= word.length <= 5 * 10^3word consists only of lowercase English letters1 <= numFriends <= word.length
Hints for Find the Lexicographically Largest String From the Box I
Hint 1
A piece can be any substring, as long as the rest of the word can still be cut into
numFriends - 1non-empty pieces.Hint 2
So a piece can be at most
n - numFriends + 1characters long, and every substring of at most that length is achievable.Hint 3
Longer is never worse for a fixed start (a prefix is smaller than the string it begins), so for each start take the longest allowed substring and keep the maximum. Handle
numFriends == 1separately.
How to solve Find the Lexicographically Largest String From the Box I
The box contains exactly the substrings of length at most L = n - numFriends + 1 (or just the whole word when numFriends == 1). Among the substrings starting at index i, the longest allowed one is the largest, because a string is larger than any of its proper prefixes. So the answer is the maximum over i of word[i .. min(i + L, n)).
Approach
- If
numFriends == 1, returnword. - Let
L = n - numFriends + 1. - For every start
i, takeword[i .. min(i + L, n))and keep the lexicographically largest.
Why it works
A piece of length len starting at i can be placed in some split iff the n - len remaining characters can form numFriends - 1 non-empty pieces, i.e. len <= L (with numFriends >= 2 there is always room on one side or both). Every achievable piece is therefore a prefix of the candidate taken at its start, and the candidate is at least as large.
Complexity
- Time —
O(n * L) - Space —
O(L)
Pitfalls
- With one friend the length bound
n - 1 + 1 = nhappens to give the whole word too, but only the start 0 is a legal piece — returnworddirectly. - Near the end of the word the candidate is shorter than
L; do not skip those starts ("ab", 2 friends → "b").
Reference solution
Python
def answerString(word: str, numFriends: int) -> str:
if numFriends == 1:
return word
n = len(word)
length = n - numFriends + 1
best = ""
for i in range(n):
cand = word[i:i + length]
if cand > best:
best = cand
return bestJava
public static String answerString(String word, int numFriends) {
if (numFriends == 1) return word;
int n = word.length(), len = n - numFriends + 1;
String best = "";
for (int i = 0; i < n; i++) {
String cand = word.substring(i, Math.min(n, i + len));
if (cand.compareTo(best) > 0) best = cand;
}
return best;
}C++
string answerString(string word, int numFriends) {
if (numFriends == 1) return word;
int n = word.size(), len = n - numFriends + 1;
string best;
for (int i = 0; i < n; i++) {
string cand = word.substr(i, len);
if (cand > best) best = cand;
}
return best;
}JavaScript
var answerString = function(word, numFriends) {
if (numFriends === 1) return word;
var n = word.length, len = n - numFriends + 1, best = "";
for (var i = 0; i < n; i++) {
var cand = word.substring(i, Math.min(n, i + len));
if (cand > best) best = cand;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique