Find the Lexicographically Largest String From the Box II

Find the Lexicographically Largest String From the Box II - Problem

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:

The string 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.

A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one.

Input & Output

Example 1 — Basic Case

$ Input: word = "abc", numFriends = 2

› Output: "bc"

💡 Note: Possible splits: ["a","bc"], ["ab","c"]. All substrings: "a", "bc", "ab", "c". The lexicographically largest is "bc".

Example 2 — Single Friend

$ Input: word = "hello", numFriends = 1

› Output: "hello"

💡 Note: With only 1 friend, the entire word goes to one person, so the answer is "hello".

Example 3 — Multiple Splits

$ Input: word = "zyab", numFriends = 3

› Output: "zyab"

💡 Note: One possible split is ["z","y","ab"]. The substring "zyab" (when we can take the whole word) is lexicographically largest.

Constraints

1 ≤ word.length ≤ 50
1 ≤ numFriends ≤ word.length
word consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

word = 'abc', numFriends = 2

All Possible Splits

Generate all ways to split into 2 non-empty parts

Collect & Compare

Find lexicographically largest substring from all splits

Key Takeaway

🎯 Key Insight: The lexicographically largest substring will always be a suffix of the original word

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is that the lexicographically largest substring will always be a valid suffix of the original string. Best approach is the optimized mathematical solution that checks each valid suffix position. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Optimization	O(n²)	O(1)	Use mathematical properties to find the lexicographically largest substring directly
Generate All Splits	O(C(n-1,k-1) × n)	O(C(n-1,k-1) × n)	Generate all possible splits and find the lexicographically largest substring

Mathematical Optimization — Algorithm Steps

Find the position of the lexicographically largest character
Check if we can create a valid split where this character starts a substring
Return the suffix starting from this optimal position

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

word = 'abc', numFriends = 2

Check Positions

For each position i ≥ numFriends-1, check suffix word[i:]

Find Maximum

Position 1 gives suffix 'bc', which is the largest valid

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* word, int numFriends) {
    int n = strlen(word);
    if (numFriends == 1) {
        char* result = (char*)malloc((n + 1) * sizeof(char));
        strcpy(result, word);
        return result;
    }
    
    char* maxString = (char*)malloc((n + 1) * sizeof(char));
    maxString[0] = '\0';
    
    // Try each position as a potential start of the largest substring
    for (int i = 0; i < n; i++) {
        // Can we split the prefix word[0:i] into numFriends-1 parts?
        if (i >= numFriends - 1) {
            char* suffix = word + i;
            if (strcmp(suffix, maxString) > 0) {
                strcpy(maxString, suffix);
            }
        }
    }
    
    return maxString;
}

int main() {
    char word[1001];
    int numFriends;
    
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    scanf("%d", &numFriends);
    
    char* result = solution(word, numFriends);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, we check each position and validate if a split is possible

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track positions and results

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

284 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler