Welcome to Subscribe On Youtube

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

  • 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) {
                int k = Math.min(n - i, n - numFriends + 1);
                String t = word.substring(i, i + k);
                if (ans.compareTo(t) < 0) {
                    ans = t;
                }
            }
            return ans;
        }
    }
    
    
  • class Solution {
    public:
        string answerString(string word, int numFriends) {
            if (numFriends == 1) {
                return word;
            }
            int n = word.size();
            string ans;
            for (int i = 0; i < n; ++i) {
                int k = min(n - i, n - numFriends + 1);
                string t = word.substr(i, k);
                ans = max(ans, t);
            }
            return ans;
        }
    };
    
    
  • class Solution:
        def answerString(self, word: str, numFriends: int) -> str:
            if numFriends == 1:
                return word
            n = len(word)
            ans = ""
            for i in range(n):
                k = min(n - i, n - numFriends + 1)
                ans = max(ans, word[i : i + k])
            return ans
    
    
  • func answerString(word string, numFriends int) (ans string) {
    	if numFriends == 1 {
    		return word
    	}
    	n := len(word)
    	for i := range word {
    		k := min(n-i, n-numFriends+1)
    		t := word[i : i+k]
    		ans = max(ans, t)
    	}
    	return
    }
    
    
  • function answerString(word: string, numFriends: number): string {
        if (numFriends === 1) {
            return word;
        }
        let ans: string = '';
        const n = word.length;
        for (let i = 0; i < n; ++i) {
            const k = Math.min(n - i, n - numFriends + 1);
            const t = word.slice(i, i + k);
            if (ans < t) {
                ans = t;
            }
        }
        return ans;
    }
    
    

All Problems

All Solutions