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.
A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one.
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 <= 2 * 105word consists only of lowercase English letters.1 <= numFriends <= word.lengthProblem Overview: You are given a string and must determine the lexicographically largest string that can be obtained according to the box rules. The core challenge is comparing candidate substrings efficiently without generating all of them.
Approach 1: Brute Force Substring Comparison (O(n^2) time, O(1) space)
Generate every possible candidate substring that could represent the final answer and compare them lexicographically. Track the maximum string seen so far using standard string comparison. This approach works because lexicographic ordering is deterministic, but repeatedly comparing long substrings leads to quadratic behavior. It is mainly useful for understanding the problem constraints or validating small test cases.
Approach 2: Two Pointers Maximum Suffix Technique (O(n) time, O(1) space)
The optimal solution scans the string using two pointers to locate the lexicographically largest suffix. Maintain two candidate start indices i and j, plus an offset k used to compare characters. If s[i + k] equals s[j + k], increase k. When a mismatch occurs, discard the weaker candidate: if s[i + k] < s[j + k], move i past the compared region; otherwise move j. Reset k after each decision. This eliminates entire ranges of inferior substrings instead of checking each one individually.
The key insight is that once a candidate prefix loses a comparison, every substring starting inside that losing region is also lexicographically smaller. Skipping those ranges guarantees linear complexity. The technique behaves like a specialized string duel between two starting positions.
This strategy is closely related to classic string algorithms used for maximum suffix detection and minimal rotation. Understanding pointer movement and substring comparison patterns is essential when solving advanced string problems and pointer‑driven scanning techniques such as two pointers.
Recommended for interviews: The two‑pointer maximum suffix method is the expected solution. A brute force explanation shows you understand lexicographic comparison, but the linear scan demonstrates strong algorithmic reasoning and familiarity with advanced string processing patterns.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Comparison | O(n^2) | O(1) | Useful for understanding the problem or validating small inputs |
| Two Pointers Maximum Suffix | O(n) | O(1) | Optimal solution for large strings and interview settings |
Practice Find the Lexicographically Largest String From the Box II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor