Find the Lexicographically Largest String From the Box I

Medium
1774.

Find the Lexicographically Largest String From the Box I

Find the Lexicographically Largest String From the Box I is a medium coding problem on strings, two pointers and enumeration, asked in Google interviews.

You are given a string word and an integer numFriends.

A game is played over several rounds. In each round word is cut into exactly numFriends non-empty pieces, in a way that no earlier round used, and every piece is put into a box. The rounds continue until every possible split has been used once.

Return the lexicographically largest string in the box after all rounds.

Example 1

Input
word = "dbca", numFriends = 2
Output
dbc
Explanation
The splits are d|bca, db|ca and dbc|a; the largest piece is "dbc".

Example 2

Input
word = "gggg", numFriends = 4
Output
g
Explanation
The only split cuts the word into four "g" pieces.

Example 3

Input
word = "abc", numFriends = 1
Output
abc
Explanation
With one friend the only piece is the whole word.

Constraints

  • 1 <= word.length <= 5 * 10^3
  • word consists only of lowercase English letters
  • 1 <= numFriends <= word.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @param {number} numFriends
 * @return {string}
 */
var answerString = function(word, numFriends) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Lexicographically Largest String From the Box I Solution

Find the Lexicographically Largest String From the Box I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Lexicographically Largest String From the Box I is a medium coding problem on strings, two pointers and enumeration, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Two Pointers, Enumeration
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string word and an integer numFriends.

A game is played over several rounds. In each round word is cut into exactly numFriends non-empty pieces, in a way that no earlier round used, and every piece is put into a box. The rounds continue until every possible split has been used once.

Return the lexicographically largest string in the box after all rounds.

Example 1

Input: word = "dbca", numFriends = 2
Output: dbc
Explanation: The splits are d|bca, db|ca and dbc|a; the largest piece is "dbc".

Example 2

Input: word = "gggg", numFriends = 4
Output: g
Explanation: The only split cuts the word into four "g" pieces.

Example 3

Input: word = "abc", numFriends = 1
Output: abc
Explanation: With one friend the only piece is the whole word.

Constraints

  • 1 <= word.length <= 5 * 10^3
  • word consists only of lowercase English letters
  • 1 <= numFriends <= word.length

Hints for Find the Lexicographically Largest String From the Box I

  1. Hint 1

    A piece can be any substring, as long as the rest of the word can still be cut into numFriends - 1 non-empty pieces.

  2. Hint 2

    So a piece can be at most n - numFriends + 1 characters long, and every substring of at most that length is achievable.

  3. Hint 3

    Longer is never worse for a fixed start (a prefix is smaller than the string it begins), so for each start take the longest allowed substring and keep the maximum. Handle numFriends == 1 separately.

How to solve Find the Lexicographically Largest String From the Box I

The box contains exactly the substrings of length at most L = n - numFriends + 1 (or just the whole word when numFriends == 1). Among the substrings starting at index i, the longest allowed one is the largest, because a string is larger than any of its proper prefixes. So the answer is the maximum over i of word[i .. min(i + L, n)).

Approach

  1. If numFriends == 1, return word.
  2. Let L = n - numFriends + 1.
  3. For every start i, take word[i .. min(i + L, n)) and keep the lexicographically largest.

Why it works

A piece of length len starting at i can be placed in some split iff the n - len remaining characters can form numFriends - 1 non-empty pieces, i.e. len <= L (with numFriends >= 2 there is always room on one side or both). Every achievable piece is therefore a prefix of the candidate taken at its start, and the candidate is at least as large.

Complexity

  • Time — O(n * L)
  • Space — O(L)

Pitfalls

  • With one friend the length bound n - 1 + 1 = n happens to give the whole word too, but only the start 0 is a legal piece — return word directly.
  • Near the end of the word the candidate is shorter than L; do not skip those starts ("ab", 2 friends → "b").

Reference solution

Python

def answerString(word: str, numFriends: int) -> str:
    if numFriends == 1:
        return word
    n = len(word)
    length = n - numFriends + 1
    best = ""
    for i in range(n):
        cand = word[i:i + length]
        if cand > best:
            best = cand
    return best

Java

public static String answerString(String word, int numFriends) {
    if (numFriends == 1) return word;
    int n = word.length(), len = n - numFriends + 1;
    String best = "";
    for (int i = 0; i < n; i++) {
        String cand = word.substring(i, Math.min(n, i + len));
        if (cand.compareTo(best) > 0) best = cand;
    }
    return best;
}

C++

string answerString(string word, int numFriends) {
    if (numFriends == 1) return word;
    int n = word.size(), len = n - numFriends + 1;
    string best;
    for (int i = 0; i < n; i++) {
        string cand = word.substr(i, len);
        if (cand > best) best = cand;
    }
    return best;
}

JavaScript

var answerString = function(word, numFriends) {
    if (numFriends === 1) return word;
    var n = word.length, len = n - numFriends + 1, best = "";
    for (var i = 0; i < n; i++) {
        var cand = word.substring(i, Math.min(n, i + len));
        if (cand > best) best = cand;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Two Pointers Technique