# Find the Lexicographically Largest String From the Box I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-lexicographically-largest-string-from-the-box-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-lexicographically-largest-string-from-the-box-i
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## Problem
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`

# Approaches
## Brute-Force Substring Generation
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Calculate the maximum possible length for a substring in a valid split: `max_len = word.length() - numFriends + 1`.
*   Initialize a string `largestString` to an empty string to keep track of the lexicographically largest substring found so far.
*   Generate all substrings of `word` with lengths from 1 up to `max_len`.
    *   This can be done with two nested loops: the outer loop for length `len` from 1 to `max_len`, and the inner loop for the starting index `i` from 0 to `word.length() - len`.
*   For each generated substring `sub`, compare it with `largestString`.
*   If `sub` is lexicographically greater than `largestString`, update `largestString` to `sub`.
*   After checking all valid substrings, `largestString` will hold the result.

## Optimized Iteration over Starting Positions
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Calculate `max_len = word.length() - numFriends + 1`.
*   Initialize an empty string `largestString`.
*   Iterate through each possible starting index `i` from 0 to `word.length() - 1`.
*   For each `i`, determine the longest valid candidate substring starting at `i`. Its length is `min(max_len, word.length() - i)`.
*   Extract this candidate substring `sub`.
*   Compare `sub` with `largestString` and update `largestString` if `sub` is lexicographically larger.
*   Return `largestString` after the loop finishes.

## Suffix-based Optimization
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.
**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.
**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.
### Explanation
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.

```java
// 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);
    }
}
```
### Algorithm
*   Calculate `max_len = word.length() - numFriends + 1`.
*   Find the starting index `k` of the lexicographically largest suffix of `word`. This can be done by:
    *   Constructing a Suffix Array for `word` in O(N log N) time. The last element of the array gives the index `k`.
    *   Alternatively, iterating through all suffixes and performing pairwise comparisons. This simpler implementation results in an O(N^2) runtime for this step.
*   Once `k` is found, the result is the prefix of this largest suffix with a length capped by `max_len`.
*   The final answer is `word.substring(k, k + min(max_len, word.length() - k))`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```