Skip to main content
Talentd

Find the Lexicographically Largest String From the Box II - Solution & Explanation

HardPremiumFree on FleetCodeTwo PointersString5 min read
Practice this problem

Problem Statement

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.

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 * 105
  • word consists only of lowercase English letters.
  • 1 <= numFriends <= word.length

Approach Overview

Problem 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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring ComparisonO(n^2)O(1)Useful for understanding the problem or validating small inputs
Two Pointers Maximum SuffixO(n)O(1)Optimal solution for large strings and interview settings

Video Solution

Leetcode 3406 (hard) - Find the Lexicographically Largest String from the Box II • TechStack in Motion • 31 views views

Frequently Asked Questions

Is Find the Lexicographically Largest String From the Box II easy or hard?
Find the Lexicographically Largest String From the Box II is classified as a Hard problem because it requires recognizing the maximum suffix pattern and implementing pointer skipping correctly. The brute force idea is simple, but achieving linear time requires deeper string algorithm insight.
Find the Lexicographically Largest String From the Box II Python/Java solution
Most implementations follow the same structure: maintain indices i, j, and offset k to compare candidate substrings. When characters differ, advance the pointer representing the smaller substring and reset the offset. This logic translates directly to Python, Java, C++, Go, or TypeScript.
How to solve Find the Lexicographically Largest String From the Box II in O(n)?
Use a maximum suffix style two-pointer scan. Maintain two candidate starting indices and compare characters using an offset. When a mismatch occurs, discard the lexicographically smaller candidate and jump its pointer past the compared region. This guarantees each character is processed only a constant number of times.
What is the best approach for Find the Lexicographically Largest String From the Box II?
The optimal approach uses a two pointers maximum suffix algorithm. Two candidate starting indices are compared character by character, and the weaker candidate is skipped entirely. This eliminates large ranges of substrings and finds the lexicographically largest result in O(n) time with O(1) extra space.
Is Find the Lexicographically Largest String From the Box II asked at Google/Amazon/Meta?
Hard string comparison and lexicographic optimization problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving suffix comparisons, greedy pointer movement, or string ranking are common in senior-level coding rounds.
What data structure is used in Find the Lexicographically Largest String From the Box II?
The solution primarily relies on string indexing and the two pointers technique. No additional data structures are required because comparisons are done directly on the input string while scanning candidate positions.
What is the time complexity of Find the Lexicographically Largest String From the Box II?
The optimal algorithm runs in O(n) time and O(1) space by scanning the string once with two moving pointers and an offset pointer for comparisons. A naive brute force approach that checks every substring requires O(n^2) time.

Ready to solve this problem?

Practice Find the Lexicographically Largest String From the Box II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Container With Most Water