Skip to main content
Talentd

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

MediumTwo PointersStringEnumeration7 min readAsked at: Amazon, Microsoft, Meta +2
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.

 

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

Approach Overview

Problem Overview: You are given a string s and an integer k. The string is split into k non‑empty substrings. Among all substrings placed in the box, return the lexicographically largest possible string that could appear.

Approach 1: Enumerate Substring Left Endpoints (O(n²) time, O(1) extra space)

The key constraint is that all k substrings must be non‑empty. If a substring starts at index i, the remaining characters must still be enough to form the other k-1 substrings. That limits the maximum length of the current substring to n - i - (k - 1). Iterate through every possible starting index and construct the longest valid substring beginning there. Compare each candidate using standard lexicographical comparison and keep the maximum.

This works because a longer prefix with a larger leading character dominates lexicographically. By always taking the maximum allowed length for each start index, you ensure the candidate is the best possible substring beginning at that position. The algorithm is straightforward: iterate through the string, compute the valid substring length, extract the candidate, and update the best answer if it is larger.

Although substring comparison can cost up to O(n), the total complexity remains O(n²) in the worst case, which is acceptable for typical constraints in medium string problems. The implementation relies entirely on basic string operations and simple iteration.

This problem mainly tests understanding of string comparison rules and careful boundary calculation while enumerating candidates. Some implementations also optimize comparisons using two pointers to avoid unnecessary substring creation, but the core idea remains enumerating valid starting points.

Recommended for interviews: Enumerating substring start positions is the expected approach. A brute-force mindset shows you understand the search space, but correctly limiting substring length using the k constraint demonstrates stronger reasoning about problem constraints and lexicographical ordering.

Solution

If we fix the left endpoint of the substring, the longer the substring, the larger its lexicographical order. Suppose the left endpoint of the substring is i, and the minimum length of the remaining substrings is numFriends - 1, then the right endpoint of the substring can be up to min(n, i + n - (numFriends - 1)), where n is the length of the string. Note that we are talking about left-closed, right-open intervals.

We enumerate all possible left endpoints, extract the corresponding substrings, compare their lexicographical order, and finally obtain the lexicographically largest substring.

The time complexity is O(n^2), and the space complexity is O(n), where n is the length of the string.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Enumerate Substring Left EndpointsO(n²)O(1)General case. Simple and reliable for typical string constraints.
Enumeration with Two-Pointer ComparisonO(n²)O(1)When avoiding substring allocations and comparing characters directly.

Video Solution

Find the Lexicographically Largest String From the Box I | Thought Process | Leetcode 3403 | MIK • codestorywithMIK • 11,029 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Lexicographically Largest String From the Box I easy or hard?
The problem is rated Medium because it combines lexicographical string comparison with constraint reasoning. The implementation itself is straightforward, but correctly determining the valid substring length based on k is the main challenge.
Find the Lexicographically Largest String From the Box I Python/Java solution
The standard implementation iterates through all starting indices, calculates the maximum valid substring length using n - i - (k - 1), extracts the candidate substring, and updates the answer if it is lexicographically larger. The same logic translates directly across Python, Java, C++, Go, and TypeScript.
How to solve Find the Lexicographically Largest String From the Box I in O(n)?
A strict O(n) solution is generally not required for this problem. Most accepted solutions enumerate substring starting positions and compare candidates, leading to O(n^2) complexity. Given the problem constraints, this approach performs efficiently in practice.
What is the best approach for Find the Lexicographically Largest String From the Box I?
The most practical approach is enumerating all possible substring starting positions while respecting the constraint that the remaining characters must still form k-1 non‑empty substrings. For each start index, take the maximum allowed length and compare the candidate lexicographically with the current best. This runs in O(n^2) time and O(1) extra space.
Is Find the Lexicographically Largest String From the Box I asked at Google/Amazon/Meta?
Problems involving lexicographical ordering and substring enumeration frequently appear in interviews at large tech companies such as Amazon, Google, and Meta. Variants often test string comparison logic, greedy reasoning, and careful handling of constraints.
What data structure is used in Find the Lexicographically Largest String From the Box I?
The solution primarily uses basic string operations and iteration. No advanced data structures are required. Some implementations use two-pointer comparisons to check lexicographic order without creating new substrings.
What is the time complexity of Find the Lexicographically Largest String From the Box I?
The typical solution runs in O(n^2) time. There are O(n) possible starting indices, and each substring comparison can take up to O(n) in the worst case. Space complexity is O(1) if comparisons are done without storing additional structures.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Construct the Lexicographically Largest Valid Sequence

Next

Last Substring in Lexicographical Order