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

Thinking

We split \(word\) into \(\textit{numFriends}\) nonempty pieces and keep the lexicographically largest piece. When \(\textit{numFriends}=1\), the whole string is the only piece.

\(n\) is modest, but enumerating every partition would compare the same substring many times. For a fixed left endpoint, a longer string is never lexicographically smaller.

The other friends take at least one character each, so a piece starting at \(i\) has length at most \(n-(\textit{numFriends}-1)\). We enumerate left endpoints, take that slice, and return the maximum among them.

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