Find the Lexicographically Largest String From the Box I
MedPrompt
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:
wordis split intonumFriendsnon-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 * 103wordconsists only of lowercase English letters.1 <= numFriends <= word.length
Approaches
3 approaches with complexity analysis and trade-offs.
This straightforward approach involves generating every possible substring that could appear in a valid split and then finding the lexicographically largest one among them. A substring is valid if its length allows the rest of the word to be split into the remaining numFriends - 1 parts. This translates to a maximum length constraint on the substrings. The algorithm iterates through all possible lengths up to this maximum, and for each length, it iterates through all possible starting positions, generating and comparing substrings.
Algorithm
- Calculate the maximum possible length for a substring in a valid split:
max_len = word.length() - numFriends + 1. - Initialize a string
largestStringto an empty string to keep track of the lexicographically largest substring found so far. - Generate all substrings of
wordwith lengths from 1 up tomax_len.- This can be done with two nested loops: the outer loop for length
lenfrom 1 tomax_len, and the inner loop for the starting indexifrom 0 toword.length() - len.
- This can be done with two nested loops: the outer loop for length
- For each generated substring
sub, compare it withlargestString. - If
subis lexicographically greater thanlargestString, updatelargestStringtosub. - After checking all valid substrings,
largestStringwill hold the result.
Walkthrough
First, we need to determine the properties of the substrings that can be part of a valid split. If we take a substring of length L from the word of length N, N - L characters remain. To form numFriends - 1 non-empty parts from these remaining characters, we need at least numFriends - 1 characters. Thus, N - L >= numFriends - 1, which simplifies to L <= N - numFriends + 1. Let this be max_len.
The brute-force algorithm systematically generates all substrings of word whose lengths are between 1 and max_len. It maintains a variable, largestString, initialized to be empty. For each generated substring, it's compared with largestString. If the new substring is lexicographically larger, largestString is updated. This process ensures that by the end of all iterations, largestString holds the overall lexicographically largest valid substring.
class Solution { public String findLexicographicallyLargestString(String word, int numFriends) { int n = word.length(); int maxLen = n - numFriends + 1; String largestString = ""; for (int len = 1; len <= maxLen; len++) { for (int i = 0; i <= n - len; i++) { String sub = word.substring(i, i + len); if (sub.compareTo(largestString) > 0) { largestString = sub; } } } return largestString; }}Complexity
Time
O(N^3), where N is the length of `word`. There are two nested loops for length and starting position, giving O(N^2) iterations. Inside the loop, substring creation and comparison each take O(N) time, leading to a total complexity of O(N^2 * N) = O(N^3).
Space
O(N), where N is the length of `word`. This space is used to store the substrings being compared. The `largestString` can have a length up to N.
Trade-offs
Pros
Simple to conceptualize and implement.
Correctly solves the problem for small inputs.
Cons
Highly inefficient due to the generation and comparison of a large number of substrings.
The time complexity of O(N^3) makes it infeasible for the given constraints, likely resulting in a 'Time Limit Exceeded' error.
This approach improves upon the brute-force method by making a key observation: for any given starting position, the longest possible valid substring is always lexicographically greater than or equal to any shorter valid substring starting at the same position. For example, "apple" is lexicographically greater than "appl". This insight allows us to avoid checking all possible lengths for each starting position, reducing the complexity significantly.
Algorithm
- Calculate
max_len = word.length() - numFriends + 1. - Initialize an empty string
largestString. - Iterate through each possible starting index
ifrom 0 toword.length() - 1. - For each
i, determine the longest valid candidate substring starting ati. Its length ismin(max_len, word.length() - i). - Extract this candidate substring
sub. - Compare
subwithlargestStringand updatelargestStringifsubis lexicographically larger. - Return
largestStringafter the loop finishes.
Walkthrough
The problem is equivalent to finding the lexicographically largest substring of word with a length no more than max_len = word.length() - numFriends + 1. Consider two substrings starting at the same index i: s1 = word[i...j] and s2 = word[i...k] with j < k. s1 is a prefix of s2, which means s1 is lexicographically smaller than s2. Therefore, for each starting position i, the only candidate we need to consider for the maximum is the longest possible valid substring, which is word.substring(i, i + min(max_len, word.length() - i)).
The algorithm iterates through all possible starting positions i from 0 to N-1. For each i, it forms the single candidate substring and compares it against the current maximum, updating it if necessary. This eliminates one level of iteration compared to the naive brute-force approach.
class Solution { public String findLexicographicallyLargestString(String word, int numFriends) { int n = word.length(); int maxLen = n - numFriends + 1; String largestString = ""; for (int i = 0; i < n; i++) { // The candidate substring from start index i has length at most maxLen // and cannot exceed the word boundary. int end = Math.min(n, i + maxLen); String sub = word.substring(i, end); if (sub.compareTo(largestString) > 0) { largestString = sub; } } return largestString; }}Complexity
Time
O(N^2), where N is the length of `word`. The main loop runs N times. Inside the loop, creating a substring of length up to N and comparing it takes O(N) time. This results in a total time complexity of O(N * N) = O(N^2).
Space
O(N), where N is the length of `word`. Space is required to store the candidate and largest substrings.
Trade-offs
Pros
Significantly more efficient than the O(N^3) approach.
Sufficiently fast to pass the given constraints.
Relatively easy to implement.
Cons
While much better than brute-force, it might still be too slow if the constraints were tighter.
It is not the most optimal solution in terms of theoretical time complexity.
This is the most efficient approach in terms of time complexity, leveraging concepts from advanced string algorithms. It's based on the same insight as the optimized O(N^2) approach but uses a more powerful tool—the Suffix Array—to speed up the search for the best candidate substring. The core idea is that the lexicographically largest candidate substring is a prefix of the lexicographically largest suffix of the entire word.
Algorithm
- Calculate
max_len = word.length() - numFriends + 1. - Find the starting index
kof the lexicographically largest suffix ofword. This can be done by:- Constructing a Suffix Array for
wordin O(N log N) time. The last element of the array gives the indexk. - Alternatively, iterating through all suffixes and performing pairwise comparisons. This simpler implementation results in an O(N^2) runtime for this step.
- Constructing a Suffix Array for
- Once
kis found, the result is the prefix of this largest suffix with a length capped bymax_len. - The final answer is
word.substring(k, k + min(max_len, word.length() - k)).
Walkthrough
The problem is to find the maximum of U_i = word.substring(i, min(n, i + max_len)) over all i. A careful analysis reveals that the lexicographical order of these candidates U_i is strongly tied to the order of the full suffixes S_i = word.substring(i). It can be shown that if S_k is the lexicographically largest suffix, then U_k will be the lexicographically largest candidate.
This reduces the problem to two steps: first, find the lexicographically largest suffix, and second, take its prefix of the allowed maximum length. While finding the largest suffix via O(N^2) pairwise comparisons is possible, a more efficient method is to use a Suffix Array. A Suffix Array can be built in O(N log N) or even O(N) time. Once built, it provides the starting indices of all suffixes in sorted lexicographical order, allowing us to identify the largest suffix's starting index in constant time.
Below is a conceptual code snippet assuming a SuffixArray class is available. A practical O(N^2) implementation that doesn't use a suffix array but follows the same logic would be identical in outcome to the previous approach.
// Assuming a SuffixArray class is available that can be constructed in O(N log N).// class SuffixArray {// int[] sa; // The suffix array// public SuffixArray(String text) { /* ... O(N log N) construction ... */ }// public int[] getSuffixArray() { return sa; }// } class Solution { public String findLexicographicallyLargestString(String word, int numFriends) { int n = word.length(); int maxLen = n - numFriends + 1; // 1. Construct Suffix Array (conceptually). // In a real contest, you might implement a simpler O(N^2) search for the max suffix // if a Suffix Array library is not available. int maxSuffixIndex = 0; for (int i = 1; i < n; i++) { if (word.substring(i).compareTo(word.substring(maxSuffixIndex)) > 0) { maxSuffixIndex = i; } } // 2. The answer is the prefix of the largest suffix. int resultLen = Math.min(maxLen, n - maxSuffixIndex); return word.substring(maxSuffixIndex, maxSuffixIndex + resultLen); }}Complexity
Time
O(N log N) or O(N log^2 N), dominated by the construction of the Suffix Array. Finding the max suffix index and extracting the final substring are comparatively fast.
Space
O(N), where N is the length of `word`. A Suffix Array and its auxiliary structures require linear space.
Trade-offs
Pros
Provides the best possible time complexity.
Demonstrates knowledge of advanced string algorithms.
Cons
Implementing a Suffix Array from scratch is complex and may not be expected in a typical coding interview setting.
A simple O(N^2) implementation of finding the max suffix offers no performance benefit over the previous approach.
Solutions
Solution
class Solution {public String answerString(String word, int numFriends) { if (numFriends == 1) { return word; } int n = word.length(); String ans = ""; for (int i = 0; i < n; ++i) { int k = Math.min(n - i, n - numFriends + 1); String t = word.substring(i, i + k); if (ans.compareTo(t) < 0) { ans = t; } } return ans; }}class Solution {public: string answerString(string word, int numFriends) { if (numFriends == 1) { return word; } int n = word.size(); string ans; for (int i = 0; i < n; ++i) { int k = min(n - i, n - numFriends + 1); string t = word.substr(i, k); ans = max(ans, t); } return ans; }};class Solution: def answerString(self, word: str, numFriends: int) -> str: if numFriends == 1: return word n = len(word) ans = "" for i in range(n): k = min(n - i, n - numFriends + 1) ans = max(ans, word[i: i + k]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.