Skip to content

3403. Find the Lexicographically Largest String From the Box I

Description

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

Solutions

Solution 1: Enumerate Substring Left Endpoints

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 \(\text{numFriends} - 1\), then the right endpoint of the substring can be up to \(\min(n, i + n - (\text{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.

1
2
3
4
5
6
class Solution:
    def answerString(self, word: str, numFriends: int) -> str:
        if numFriends == 1:
            return word
        n = len(word)
        return max(word[i : i + n - (numFriends - 1)] for i in range(n))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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) {
            String t = word.substring(i, Math.min(n, i + n - (numFriends - 1)));
            if (ans.compareTo(t) < 0) {
                ans = t;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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) {
            string t = word.substr(i, min(n - i, n - (numFriends - 1)));
            if (ans < t) {
                ans = t;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func answerString(word string, numFriends int) (ans string) {
    if numFriends == 1 {
        return word
    }
    n := len(word)
    for i := 0; i < n; i++ {
        t := word[i:min(n, i+n-(numFriends-1))]
        ans = max(ans, t)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function answerString(word: string, numFriends: number): string {
    if (numFriends === 1) {
        return word;
    }
    const n = word.length;
    let ans = '';
    for (let i = 0; i < n; i++) {
        const t = word.slice(i, Math.min(n, i + n - (numFriends - 1)));
        ans = t > ans ? t : ans;
    }
    return ans;
}

Comments