Skip to content

3683. Find The Lexicographically Largest String From The Box I

Difficulty: Medium

LeetCode Problem View on GitHub

3683. Find the Lexicographically Largest String From the Box I

Medium

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

Solution

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    private ArrayList<String> ans;

    public String answerString(String word, int numFriends) {
        int n = word.length();
        ans = new ArrayList<>();
        if (numFriends == 1)
            return word;
        int ind = -1;
        int count = 0;
        char ch = 'a';
        ArrayList<Integer> idx = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (word.charAt(i) > ch) {
                ch = word.charAt(i);
            }
        }
        for (int i = 0; i < n; i++) {
            if (word.charAt(i) == ch)
                idx.add(i);
        }
        for (int ele : idx)
            solve(ele, word, numFriends);
        Collections.sort(ans);
        if (ans.size() == 0)
            return "";
        return ans.get(ans.size() - 1);
    }

    private void solve(int ind, String word, int numFriends) {
        int n = word.length();
        int count_prev = ind;
        StringBuilder res = new StringBuilder();
        if (count_prev >= numFriends) {
            for (int i = ind; i < n; i++)
                res.append(word.charAt(i));
            ans.add(res.toString());
        } else {
            int req = numFriends - count_prev - 1;
            for (int i = n - 1 - req; i >= ind; i--) {
                res.append(word.charAt(i));
            }
            ans.add(res.reverse().toString());
        }
    }
}

Complexity Analysis

  • Time Complexity: O(?)
  • Space Complexity: O(?)

Approach

Detailed explanation of the approach will be added here