Find the Lexicographically Largest String From the Box II

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.

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:

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
5
6
7
8


Input: word = "gggg", numFriends = 4
Output: "g"
Explanation:
The only possible split is: "g", "g", "g", and "g".
### Constraint
- `1 <= word.length <= 2 * 105`
- `word` consists only of lowercase English letters.
- `1 <= numFriends <= word.length`

Solution

Method 1 – Greedy Split and Max Substring

Intuition

For each possible split of the string into numFriends non-empty parts, the largest string in the box is always the lexicographically largest substring among all possible splits. For each split, the largest part is always a contiguous substring, so we can try all possible splits and track the largest substring.

Approach

Generate all possible ways to split the string into numFriends non-empty parts (using combinations of split points).
For each split, collect all parts and track the lexicographically largest part among all splits.
Return the largest string found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
public:
    string getMaxString(string word, int numFriends) {
        int n = word.size(), ansStart = 0, ansLen = 1;
        vector<int> split(numFriends-1);
        function<void(int, int)> dfs = [&](int idx, int last) {
            if (idx == numFriends-1) {
                vector<int> cuts = {0};
                cuts.insert(cuts.end(), split.begin(), split.end());
                cuts.push_back(n);
                for (int i = 0; i < numFriends; ++i) {
                    int l = cuts[i], r = cuts[i+1];
                    if (r-l > ansLen || (r-l == ansLen && word.substr(l, r-l) > word.substr(ansStart, ansLen))) {
                        ansStart = l; ansLen = r-l;
                    }
                }
                return;
            }
            for (int i = last+1; i < n-(numFriends-idx-1); ++i) {
                split[idx] = i;
                dfs(idx+1, i);
            }
        };
        dfs(0, 0);
        return word.substr(ansStart, ansLen);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func getMaxString(word string, numFriends int) string {
    n := len(word)
    ans := word[:1]
    var dfs func(idx, last int, split []int)
    dfs = func(idx, last int, split []int) {
        if idx == numFriends-1 {
            cuts := append([]int{0}, split...)
            cuts = append(cuts, n)
            for i := 0; i < numFriends; i++ {
                l, r := cuts[i], cuts[i+1]
                if r-l > len(ans) || (r-l == len(ans) && word[l:r] > ans) {
                    ans = word[l:r]
                }
            }
            return
        }
        for i := last+1; i < n-(numFriends-idx-1); i++ {
            dfs(idx+1, i, append(split, i))
        }
    }
    dfs(0, 0, []int{})
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
    public String getMaxString(String word, int numFriends) {
        int n = word.length();
        String ans = word.substring(0, 1);
        List<Integer> split = new ArrayList<>();
        dfs(0, 0, split);
        return ans;
    }
    String ans;
    void dfs(int idx, int last, List<Integer> split) {
        int n = ans.length();
        if (idx == n-1) {
            List<Integer> cuts = new ArrayList<>();
            cuts.add(0); cuts.addAll(split); cuts.add(n);
            for (int i = 0; i < n; i++) {
                int l = cuts.get(i), r = cuts.get(i+1);
                String s = ans.substring(l, r);
                if (s.length() > ans.length() || (s.length() == ans.length() && s.compareTo(ans) > 0)) ans = s;
            }
            return;
        }
        for (int i = last+1; i < n-(n-idx-1); i++) {
            split.add(i);
            dfs(idx+1, i, split);
            split.remove(split.size()-1);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    fun getMaxString(word: String, numFriends: Int): String {
        val n = word.length
        var ans = word.substring(0, 1)
        fun dfs(idx: Int, last: Int, split: MutableList<Int>) {
            if (idx == numFriends-1) {
                val cuts = mutableListOf(0); cuts.addAll(split); cuts.add(n)
                for (i in 0 until numFriends) {
                    val l = cuts[i]; val r = cuts[i+1]
                    val s = word.substring(l, r)
                    if (s.length > ans.length || (s.length == ans.length && s > ans)) ans = s
                }
                return
            }
            for (i in last+1 until n-(numFriends-idx-1)) {
                split.add(i)
                dfs(idx+1, i, split)
                split.removeAt(split.size-1)
            }
        }
        dfs(0, 0, mutableListOf())
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def get_max_string(word: str, numFriends: int) -> str:
    n = len(word)
    ans = word[0]
    def dfs(idx: int, last: int, split: list[int]):
        nonlocal ans
        if idx == numFriends-1:
            cuts = [0] + split + [n]
            for i in range(numFriends):
                l, r = cuts[i], cuts[i+1]
                s = word[l:r]
                if len(s) > len(ans) or (len(s) == len(ans) and s > ans):
                    ans = s
            return
        for i in range(last+1, n-(numFriends-idx-1)):
            dfs(idx+1, i, split+[i])
    dfs(0, 0, [])
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


impl Solution {
    pub fn get_max_string(word: String, num_friends: i32) -> String {
        let n = word.len();
        let mut ans = word[0..1].to_string();
        let word_bytes = word.as_bytes();
        fn dfs(idx: usize, last: usize, split: &mut Vec<usize>, n: usize, num_friends: usize, word_bytes: &[u8], ans: &mut String) {
            if idx == num_friends-1 {
                let mut cuts = vec![0];
                cuts.extend(split.iter().cloned());
                cuts.push(n);
                for i in 0..num_friends {
                    let l = cuts[i]; let r = cuts[i+1];
                    let s = &word_bytes[l..r];
                    let s_str = std::str::from_utf8(s).unwrap();
                    if s_str.len() > ans.len() || (s_str.len() == ans.len() && s_str > ans.as_str()) {
                        *ans = s_str.to_string();
                    }
                }
                return;
            }
            for i in last+1..n-(num_friends-idx-1) {
                split.push(i);
                dfs(idx+1, i, split, n, num_friends, word_bytes, ans);
                split.pop();
            }
        }
        dfs(0, 0, &mut vec![], n, num_friends as usize, word_bytes, &mut ans);
        ans
    }
}

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


class Solution {
    getMaxString(word: string, numFriends: number): string {
        const n = word.length;
        let ans = word[0];
        function dfs(idx: number, last: number, split: number[]) {
            if (idx === numFriends-1) {
                const cuts = [0, ...split, n];
                for (let i = 0; i < numFriends; i++) {
                    const l = cuts[i], r = cuts[i+1];
                    const s = word.slice(l, r);
                    if (s.length > ans.length || (s.length === ans.length && s > ans)) ans = s;
                }
                return;
            }
            for (let i = last+1; i < n-(numFriends-idx-1); i++) {
                dfs(idx+1, i, [...split, i]);
            }
        }
        dfs(0, 0, []);
        return ans;
    }
}

Complexity

⏰ Time complexity: O(C(n-1, numFriends-1) * n), as we try all splits and check all parts.
🧺 Space complexity: O(n), for recursion and split arrays.

Problem#

Example 1:#

Example 2:#

Solution#

Method 1 – Greedy Split and Max Substring#

Intuition#

Approach#

Code#

Complexity#