LeetCode Problem 3406

Difficulty: 🔴 Hard
Topics: Two Pointers, String

Solution

LeetCode 3406 - Find the Lexicographically Largest String From the Box II

Problem Understanding

We are given a string word of length n and an integer numFriends.

In every round, Alice splits the entire string into exactly numFriends non-empty pieces. Every possible valid split is considered exactly once. Every piece produced by every split is placed into a box.

After all possible splits have been processed, we must find the lexicographically largest string that ever appeared in the box.

The key observation is that the box contains individual pieces, not entire split configurations. We only care whether a particular substring can appear as one of the pieces in some valid split.

The constraints are very large:

• 1 <= n <= 2 * 10^5
• The string contains only lowercase English letters.

Since the string can contain up to 200,000 characters, any solution that explicitly generates all splits or compares large numbers of substrings will be too slow.

Several edge cases are important:

• When numFriends == 1, the only possible split is the entire string itself.
• When numFriends == n, every piece must have length 1, so the answer is simply the largest character in the string.
• Large strings with many repeated characters can cause quadratic behavior in naive lexicographical comparisons.

Problem Understanding

This problem is asking us to determine the lexicographically largest string that can appear in a box after splitting a given string word into numFriends non-empty contiguous substrings in all possible ways. Each round produces splits of word such that no two splits are exactly the same, and all resulting substrings are added to the box. The goal is to find the maximum string according to lexicographical order across all substrings that have ever been placed in the box.

The input word is a lowercase English string of length up to 200,000 characters. numFriends is an integer between 1 and the length of word. The output is a string from word that is lexicographically largest among all possible substrings generated by splitting.

Edge cases include when numFriends equals the length of the string, which produces only one possible split where every character is a substring, or when numFriends is 1, which produces the entire word as the only substring. These constraints indicate that generating all possible splits explicitly would be computationally infeasible, since the number of splits grows combinatorially with the string length.

Approaches

Brute Force

A brute force solution would enumerate every possible way to place numFriends - 1 cut positions among the n - 1 gaps in the string.

For each split:

1. Generate all pieces.
2. Insert them into a collection.
3. Track the lexicographically largest piece seen so far.

This is correct because it directly follows the problem statement. However, the number of valid splits is enormous:

$$\binom{n-1}{numFriends-1}$$

Even for moderate values of n, this becomes completely infeasible.

Key Insight

Suppose a piece starts at position i.

If that piece has length L, then the remaining characters are:

$$n - L$$

Those remaining characters must be distributed among the other numFriends - 1 pieces, each of which must be non-empty.

Therefore:

$$n - L \ge numFriends - 1$$

which gives:

$$L \le n - numFriends + 1$$

Let

$$m = n - numFriends + 1$$

Then any piece beginning at index i can have length at most:

$$\min(m,\ n-i)$$

For a fixed starting position i, the lexicographically largest piece is simply the longest valid one:

$$word[i : i + \min(m,\ n-i)]$$

because extending a string by additional characters always makes it lexicographically larger than its own prefix.

So the problem becomes:

Find the lexicographically largest string among all candidates

$$word[i : i + \min(m,\ n-i)]$$

for every starting position i.

A further observation simplifies things even more. The winner is determined by the lexicographically largest suffix of word.

If the largest suffix starts at position best, then the answer is simply the first m characters of that suffix, or the whole suffix if it is shorter.

Finding the lexicographically maximum suffix can be done in linear time using the classic two-pointer maximum-suffix algorithm.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates all valid splits
Optimal	O(n)	O(1)	Finds the lexicographically maximum suffix using two pointers

Algorithm Walkthrough

1. Let n = len(word).
2. Compute:

$$m = n - numFriends + 1$$

This is the maximum possible length of any piece. 3. Use the maximum-suffix algorithm.

Maintain two candidate suffix starts:

• i, current best suffix
• j, competing suffix

Also maintain an offset k indicating how many characters have matched so far. 4. Compare characters:

• If word[i + k] == word[j + k], increment k.
• If word[i + k] < word[j + k], suffix j is better, so discard all positions from i through i + k.
• If word[i + k] > word[j + k], suffix i remains better, so discard all positions from j through j + k.

5. Continue until one candidate runs past the end of the string.
6. The surviving position is the start of the lexicographically largest suffix.
7. Return:

word[best : min(n, best + m)]

Why it works

For every starting position, the best obtainable piece is the longest valid substring beginning there. Comparing these candidates is equivalent to comparing the corresponding suffixes. Therefore the answer comes from the lexicographically largest suffix of the string. The maximum-suffix algorithm correctly finds that suffix in linear time by eliminating ranges of starting positions that can never beat the current best candidate. The brute-force approach would enumerate all possible ways to split word into numFriends contiguous non-empty substrings. For each split, we would add all the substrings to a box and then find the lexicographically largest string from the box. While correct, this approach is far too slow for large inputs. Generating all splits involves combinatorial enumeration, which can grow on the order of $O(\binom{n-1}{k-1})$ for a string of length $n$ split into $k$ substrings. With $n$ up to 200,000, this is computationally impossible.

Key Insight for Optimal Solution

The critical observation is that among all possible splits, the lexicographically largest substring always appears as a prefix in one of the splits. Specifically, to maximize the string, we want to choose the earliest prefix that is as long as possible and larger than any alternative prefix. This allows us to avoid generating all splits entirely.

Given that all splits must consist of non-empty substrings, the lexicographically largest string in the box will always be the largest substring that starts at the first character and ends before the final substring in a split. Thus, the problem reduces to scanning the string and finding the largest prefix among all valid lengths for numFriends.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n choose k)	O(n choose k)	Generate all possible splits and all substrings, then take max
Optimal	O(n)	O(1)	Only track the largest substring prefix while scanning once

Algorithm Walkthrough

1. Initialize a variable max_str as an empty string. This will hold the lexicographically largest string found so far.
2. Iterate over the first len(word) - numFriends + 1 characters of word. Each position i represents a potential endpoint for the first substring in a split, ensuring that there are at least numFriends - 1 characters remaining to form the remaining substrings.
3. For each position i, extract the substring word[0:i+1].
4. Compare this substring with max_str lexicographically. If it is larger, update max_str.
5. After completing the loop, max_str will contain the lexicographically largest substring that could appear in any split.

Why it works: The algorithm guarantees that every candidate substring that could become the first part of some split is considered. Since any substring not starting at index 0 would appear as a later part of some split, it cannot exceed the lexicographical value of a prefix starting at index 0. This invariant ensures correctness.

Python Solution

class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        n = len(word)
        max_len = n - numFriends + 1

        i, j, k = 0, 1, 0

        while j + k < n:
            if word[i + k] == word[j + k]:
                k += 1
            elif word[i + k] < word[j + k]:
                i = max(i + k + 1, j)
                j = i + 1
                k = 0
            else:
                j = j + k + 1
                k = 0

        best = i
        return word[best:min(n, best + max_len)]

Implementation Explanation

The variable max_len stores the maximum length any valid piece can have.

The core of the solution is the maximum-suffix algorithm. Two suffixes are compared simultaneously using pointers i and j. The offset k tracks how many characters currently match.

Whenever a mismatch occurs, one of the suffixes is proven inferior and an entire block of starting positions can be skipped. This guarantees linear running time.

After the loop finishes, i points to the lexicographically largest suffix. The final answer is the longest valid piece starting from that position, which is obtained by truncating the suffix to length max_len. max_str = "" # We only consider prefixes that leave at least numFriends-1 characters for i in range(n - numFriends + 1): current = word[:i + 1] if current > max_str: max_str = current return max_str

This implementation scans prefixes of `word` up to a length that guarantees each split has at least one character. For each prefix, it updates the `max_str` if the current prefix is lexicographically larger. By the end of the loop, `max_str` contains the answer.

## Go Solution

```go
func answerString(word string, numFriends int) string {
	n := len(word)
	maxLen := n - numFriends + 1

	i, j, k := 0, 1, 0

	for j+k < n {
		if word[i+k] == word[j+k] {
			k++
		} else if word[i+k] < word[j+k] {
			if i+k+1 > j {
				i = i + k + 1
			} else {
				i = j
			}
			j = i + 1
			k = 0
		} else {
			j = j + k + 1
			k = 0
		}
	}

	best := i
	end := best + maxLen
	if end > n {
		end = n
	}

	return word[best:end]
}

Go-Specific Notes

The Go implementation follows exactly the same logic as the Python version.

Since strings in Go are byte slices internally and the input consists only of lowercase English letters, direct indexing with word[i] is safe and efficient.

No special handling for integer overflow is required because all indices remain within the string length, which is at most 2 * 10^5.

Worked Examples

Example 1

Input:

word = "dbca"
numFriends = 2

Compute:

n = 4
max_len = 3

Candidate pieces:

Start	Candidate
0	"dbc"
1	"bca"
2	"ca"
3	"a"

The lexicographically largest suffix is:

"dbca"

starting at index 0.

Therefore:

answer = word[0:3] = "dbc"

Output:

"dbc"

Example 2

Input:

word = "gggg"
numFriends = 4

Compute:

n = 4
max_len = 1

Candidate pieces:

Start	Candidate
0	"g"
1	"g"
2	"g"
3	"g"

All candidates are identical.

The returned value is:

"g"

Output:

"g"

n := len(word)
maxStr := ""
for i := 0; i <= n - numFriends; i++ {
    current := word[:i+1]
    if current > maxStr {
        maxStr = current
    }
}
return maxStr

}

In Go, string slicing behaves similarly to Python, so we can iterate over prefix lengths directly. We initialize `maxStr` as an empty string and update it whenever a larger prefix is found. The bounds of the loop ensure that at least `numFriends - 1` characters remain for other substrings.

## Worked Examples

### Example 1: word = "dbca", numFriends = 2

| Step | i | Current Prefix | max_str |
| --- | --- | --- | --- |
| 1 | 0 | "d" | "d" |
| 2 | 1 | "db" | "db" |
| 3 | 2 | "dbc" | "dbc" |

Output: `"dbc"`

### Example 2: word = "gggg", numFriends = 4

| Step | i | Current Prefix | max_str |
| --- | --- | --- | --- |
| 1 | 0 | "g" | "g" |

Output: `"g"`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | Maximum-suffix algorithm processes each position a constant number of times |
| Space | O(1) | Only a few index variables are stored |

The crucial optimization is that the two-pointer maximum-suffix algorithm never revisits discarded ranges of indices. Each character participates in only a constant amount of work, giving an overall linear running time, which easily handles strings of length up to `200,000`.
| Time | O(n) | We iterate through at most n prefixes of the string once |
| Space | O(1) | Only a single string variable is used to track the maximum |

The reasoning is that we do not generate all possible splits or substrings; we only track the largest prefix candidate.

## Test Cases

sol = Solution()

assert sol.answerString("dbca", 2) == "dbc" # example 1 assert sol.answerString("gggg", 4) == "g" # example 2

assert sol.answerString("a", 1) == "a" # single character assert sol.answerString("abcd", 1) == "abcd" # entire string must be returned

assert sol.answerString("babb", 4) == "b" # every piece length 1 assert sol.answerString("zzza", 4) == "z" # largest character

assert sol.answerString("aaaaa", 2) == "aaaa" # repeated characters assert sol.answerString("abcde", 2) == "de" # best suffix near end

assert sol.answerString("leetcode", 3) == "tcode" # internal maximum suffix

assert sol.answerString("cba", 2) == "cb" # decreasing characters assert sol.answerString("ababab", 3) == "babab" # alternating pattern

assert sol.answerString("zzzzzz", 1) == "zzzzzz" # numFriends = 1 assert sol.answerString("zzzzzz", 6) == "z" # numFriends = n

### Test Summary

| Test | Why |
| --- | --- |
| `("dbca", 2)` | Official example |
| `("gggg", 4)` | Official example |
| `("a", 1)` | Smallest input |
| `("abcd", 1)` | Entire string returned |
| `("babb", 4)` | All pieces length 1 |
| `("zzza", 4)` | Maximum character selection |
| `("aaaaa", 2)` | Repeated characters |
| `("abcde", 2)` | Best answer comes from near the end |
| `("leetcode", 3)` | General mixed string |
| `("cba", 2)` | Descending characters |
| `("ababab", 3)` | Alternating pattern |
| `("zzzzzz", 1)` | Minimum number of friends |
| `("zzzzzz", 6)` | Maximum number of friends |

## Edge Cases

### `numFriends == 1`

When there is only one friend, the entire string must remain as a single piece. A common mistake is to continue applying substring restrictions even though no cuts are required. In this case:

max_len = n

so the algorithm naturally returns the entire string.

### `numFriends == n`

Every piece must contain exactly one character. The answer becomes the largest character appearing in the string. The formula:

max_len = n - n + 1 = 1

automatically enforces this restriction, so the algorithm returns a single-character substring.

### Large Blocks of Equal Characters

Strings such as:

"aaaaaaaaaaaaaaaa..."

can cause quadratic behavior in naive substring comparisons because many prefixes match. The maximum-suffix algorithm handles these efficiently by advancing pointers in blocks, guaranteeing linear time even when long common prefixes exist.

### Best Answer Near the End of the String

The lexicographically largest suffix may start very close to the end, producing a candidate shorter than `max_len`. For example:

word = "abcde" numFriends = 2

The winning suffix starts at `'d'`, and only `"de"` is available. The implementation correctly truncates using:

min(n, best + max_len)

so it never reads past the end of the string.
s = Solution()

# Example test cases
assert s.answerString("dbca", 2) == "dbc"  # largest prefix leaving one character
assert s.answerString("gggg", 4) == "g"   # only one valid split, all single chars

# Edge cases
assert s.answerString("a", 1) == "a"      # smallest string possible
assert s.answerString("abcde", 1) == "abcde"  # entire string is the only substring
assert s.answerString("abcde", 5) == "a"      # every char is a substring

# Larger string
assert s.answerString("zxyabc", 3) == "zxy"   # largest prefix that allows splits
assert s.answerString("ababab", 2) == "ababa" # ensure correct prefix selection

Test	Why
"dbca", 2	Validates standard example
"gggg", 4	Validates when all splits are single chars
"a", 1	Minimal input edge case
"abcde", 1	Only one substring in the split
"abcde", 5	Split into single chars, must pick first
"zxyabc", 3	Checks prefix selection with longer string
"ababab", 2	Checks correct selection of prefix in repeated patterns

Edge Cases

First, consider the case where numFriends equals the length of word. Here, each split produces single-character substrings. A naive solution might attempt to generate splits and fail, but our prefix approach correctly selects the first character as the largest substring, which is guaranteed to appear in the box.

Second, if numFriends is 1, the only substring generated is the entire string. Any algorithm that fails to consider the single-substring scenario might return an incorrect result, but our approach handles it naturally because the loop considers the entire word as a prefix candidate.

Finally, when word contains repeated characters, such as "aaaaaa", a naive lexicographical comparison might not correctly handle equality cases. Our implementation correctly updates max_str only when a strictly larger string is found, ensuring that the final output is accurate even when multiple substrings are identical.