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 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: Greedy

• Time complexity: O(n²)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} word
 * @param {number} numFriends
 * @return {string}
 */
const answerString = function (word, numFriends) {
  if (numFriends === 1) return word;
  const n = word.length;
  let result = '';

  for (let index = 0; index < n; index++) {
    if (result[0] > word[index]) continue;
    const needSplit = Math.max(numFriends - index - 1, 0);
    const splitWord = word.slice(index, n - needSplit);

    if (splitWord > result) {
      result = splitWord;
    }
  }

  return result;
};