Find the Lexicographically Largest String From the Box I

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.

Examples

Example 1

1
2
3
4
5
6
7
Input: word = "dbca", numFriends = 2
Output: "dbc"
Explanation:
All possible splits are:
  * `"d"` and `"bca"`.
  * `"db"` and `"ca"`.
  * `"dbc"` and `"a"`.

Example 2

1
2
3
4
Input: word = "gggg", numFriends = 4
Output: "g"
Explanation:
The only possible split is: `"g"`, `"g"`, `"g"`, and `"g"`.

Constraints

1 <= word.length <= 5 * 10^3
word consists only of lowercase English letters.
1 <= numFriends <= word.length

Solution

Method 1 – Enumeration of All Splits

We need to find the lexicographically largest substring that can result from splitting word into numFriends non-empty parts. Lexicographical order is the same as dictionary order: for example, “bc” > “ab” because “b” comes after “a”, and “abcd” > “abc” since it has an extra character at the end. This means we should look for the longest possible substring after making the required splits. Since the string is divided into numFriends parts, the longest substring possible is of length word.length() - numFriends + 1. To solve this, we can check all substrings of lengths from 1 up to word.length() - numFriends + 1 and return the largest one in lexicographical order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string answerString(string word, int numFriends) {
        if (numFriends == 1) return word;
        int n = word.size();
        string ans = "";
        int maxLen = n - numFriends + 1;
        for (int i = 0; i < n; ++i) {
            string sub;
            if (i + maxLen <= n)
                sub = word.substr(i, maxLen);
            else
                sub = word.substr(i);
            if (sub > ans)
                ans = sub;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
type Solution struct{}

func (Solution) AnswerString(word string, numFriends int) string {
    if numFriends == 1 {
        return word
    }
    n := len(word)
    ans := ""
    maxLen := n - numFriends + 1
    for i := 0; i < n; i++ {
        var sub string
        if i+maxLen <= n {
            sub = word[i : i+maxLen]
        } else {
            sub = word[i:]
        }
        if sub > ans {
            ans = sub
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public String answerString(String word, int numFriends) {
        if (numFriends == 1) return word;
        int n = word.length();
        String ans = "";
        int maxLen = n - numFriends + 1;
        for (int i = 0; i < n; i++) {
            String sub;
            if (i + maxLen <= n)
                sub = word.substring(i, i + maxLen);
            else
                sub = word.substring(i);
            if (sub.compareTo(ans) > 0)
                ans = sub;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    fun answerString(word: String, numFriends: Int): String {
        if (numFriends == 1) return word
        val n = word.length
        var ans = ""
        val maxLen = n - numFriends + 1
        for (i in 0 until n) {
            val sub = if (i + maxLen <= n) word.substring(i, i + maxLen) else word.substring(i)
            if (sub > ans) ans = sub
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        if numFriends == 1:
            return word
        n = len(word)
        ans = ""
        maxLen = n - numFriends + 1
        for i in range(n):
            if i + maxLen <= n:
                sub = word[i:i+maxLen]
            else:
                sub = word[i:]
            if sub > ans:
                ans = sub
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn answer_string(word: String, num_friends: i32) -> String {
        if num_friends == 1 {
            return word;
        }
        let n = word.len();
        let max_len = n - num_friends as usize + 1;
        let bytes = word.as_bytes();
        let mut ans = "";
        for i in 0..n {
            let end = if i + max_len <= n { i + max_len } else { n };
            let sub = &word[i..end];
            if sub > ans {
                ans = sub;
            }
        }
        ans.to_string()
    }
}

Complexity

⏰ Time complexity: O(n * maxLen), - where n = length of word and maxLen = word.length() - numFriends + 1 (the length of the substring window)
- For each of the n starting indices, you extract a substring of up to maxLen and compare it to the current answer.
- In the worst case, substring extraction and comparison is O(maxLen) per iteration.
- So, overall time complexity: O(n × (n - numFriends + 1)) For large numFriends, this approaches O(n); for small numFriends, it approaches O(n²).
🧺 Space complexity: O(n)
- O(maxLen) for storing the current substring and answer.
- No extra data structures are used that grow with input size.
- Overall space complexity: O(n) (since maxLen ≤ n)

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Enumeration of All Splits#

Code#

Complexity#